Java Program to Implement Rabin-Karp Method for Pattern Searching

This is a Java Program to Implement Rabin Karp Pattern Matching Algorithm. The Rabin–Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text.

Here is the source code of the Java Program to Implement Rabin Karp Pattern Matching Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. `/**`
2. ` ** Java Program to Implement Rabin Karp Pattern Matching Algorithm`
3. ` **/`
4. ` `
5. `import java.io.BufferedReader;`
6. `import java.io.InputStreamReader;`
7. `import java.io.IOException;`
8. `import java.util.Random;`
9. `import java.math.BigInteger;`
10. ` `
11. `public class RabinKarp `
12. `{`
13. `    /** String Pattern **/`
14. `    private String pat; `
15. `    /** pattern hash value **/    `
16. `    private long patHash;    `
17. `    /** pattern length **/`
18. `    private int M;  `
19. `    /** Large prime **/         `
20. `    private long Q; `
21. `    /** radix **/         `
22. `    private int R;   `
23. `    /** R^(M-1) % Q **/        `
24. `    private long RM;          `
25. ` `
26. `    /** Constructor **/`
27. `    public RabinKarp(String txt, String pat) `
28. `    {`
29. `        this.pat = pat;      `
30. `        R = 256;`
31. `        M = pat.length();`
32. `        Q = longRandomPrime();`
33. `        /** precompute R^(M-1) % Q for use in removing leading digit **/`
34. `        RM = 1;`
35. `        for (int i = 1; i <= M-1; i++)`
36. `           RM = (R * RM) % Q;`
37. `        patHash = hash(pat, M);`
38. `        int pos = search(txt);`
39. `        if (pos == -1)`
40. `            System.out.println("\nNo Match\n");`
41. `        else`
42. `            System.out.println("Pattern found at position : "+ pos);`
43. `    } `
44. `    /** Compute hash **/`
45. `    private long hash(String key, int M)`
46. `    { `
47. `        long h = 0; `
48. `        for (int j = 0; j < M; j++) `
49. `            h = (R * h + key.charAt(j)) % Q; `
50. `        return h; `
51. `    } `
52. `    /** Funtion check **/`
53. `    private boolean check(String txt, int i) `
54. `    {`
55. `        for (int j = 0; j < M; j++) `
56. `            if (pat.charAt(j) != txt.charAt(i + j)) `
57. `                return false; `
58. `        return true;`
59. `    }`
60. `    /** Funtion to check for exact match**/`
61. `    private int search(String txt) `
62. `    {`
63. `        int N = txt.length(); `
64. `        if (N < M) return N;`
65. `        long txtHash = hash(txt, M); `
66. `        /** check for match at start **/`
67. `        if ((patHash == txtHash) && check(txt, 0))`
68. `            return 0;`
69. `        /** check for hash match. if hash match then check for exact match**/`
70. `        for (int i = M; i < N; i++) `
71. `        {`
72. `            // Remove leading digit, add trailing digit, check for match. `
73. `            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q; `
74. `            txtHash = (txtHash * R + txt.charAt(i)) % Q; `
75. `            // match`
76. `            int offset = i - M + 1;`
77. `            if ((patHash == txtHash) && check(txt, offset))`
78. `                return offset;`
79. `        }`
80. `        /** no match **/`
81. `        return -1;`
82. `    }`
83. `    /** generate a random 31 bit prime **/`
84. `    private static long longRandomPrime() `
85. `    {`
86. `        BigInteger prime = BigInteger.probablePrime(31, new Random());`
87. `        return prime.longValue();`
88. `    }`
89. `    /** Main Function **/`
90. `    public static void main(String[] args) throws IOException`
91. `    {    `
92. `        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));`
93. `        System.out.println("Rabin Karp Algorithm Test\n");`
94. `        System.out.println("\nEnter Text\n");`
95. `        String text = br.readLine();`
96. `        System.out.println("\nEnter Pattern\n");`
97. `        String pattern = br.readLine();`
98. `        System.out.println("\nResults : \n");`
99. `        RabinKarp rk = new RabinKarp(text, pattern);        `
100. `    }`
101. `}`

```Rabin Karp Algorithm Test

Enter Text

abcdefghijklmnopqrstuvwxyz

Enter Pattern

jklmn

Results :

Pattern found at position : 9```

Sanfoundry Global Education & Learning Series – 1000 Java Programs.