| 4 | public final static int d = 10; |
| 5 | |
| 6 | static void search(String pattern, String txt, int q) { |
| 7 | int m = pattern.length(); |
| 8 | int n = txt.length(); |
| 9 | int i, j; |
| 10 | int p = 0; |
| 11 | int t = 0; |
| 12 | int h = 1; |
| 13 | |
| 14 | for (i = 0; i < m - 1; i++) |
| 15 | h = (h * d) % q; |
| 16 | |
| 17 | // Calculate hash value for pattern and text |
| 18 | for (i = 0; i < m; i++) { |
| 19 | p = (d * p + pattern.charAt(i)) % q; |
| 20 | t = (d * t + txt.charAt(i)) % q; |
| 21 | } |
| 22 | |
| 23 | // Find the match |
| 24 | for (i = 0; i <= n - m; i++) { |
| 25 | if (p == t) { |
| 26 | for (j = 0; j < m; j++) { |
| 27 | if (txt.charAt(i + j) != pattern.charAt(j)) |
| 28 | break; |
| 29 | } |
| 30 | |
| 31 | if (j == m) |
| 32 | System.out.println("Pattern is found at position: " + (i + 1)); |
| 33 | } |
| 34 | |
| 35 | if (i < n - m) { |
| 36 | t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; |
| 37 | if (t < 0) |
| 38 | t = (t + q); |
| 39 | } |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | public static void main(String[] args) { |
| 44 | String txt = "ABCCDDAEFG"; |