RabinKarp.java

packagecom.thealgorithms.strings;

importjava.util.Scanner;

/**
 * @author Prateek Kumar Oraon (https://github.com/prateekKrOraon)
 *
 An implementation of Rabin-Karp string matching algorithm
 Program will simply end if there is no match
 */
publicfinalclassRabinKarp {
privateRabinKarp() {
 }

publicstaticScannerscanner = null;
publicstaticfinalintALPHABET_SIZE = 256;

publicstaticvoidmain(String[] args) {
scanner = newScanner(System.in);
System.out.println("Enter String");
Stringtext = scanner.nextLine();
System.out.println("Enter pattern");
Stringpattern = scanner.nextLine();

intq = 101;
searchPat(text, pattern, q);
 }

privatestaticvoidsearchPat(Stringtext, Stringpattern, intq) {
intm = pattern.length();
intn = text.length();
intt = 0;
intp = 0;
inth = 1;
intj = 0;
inti = 0;

h = (int) Math.pow(ALPHABET_SIZE, m - 1) % q;

for (i = 0; i < m; i++) {
// hash value is calculated for each character and then added with the hash value of the
// next character for pattern as well as the text for length equal to the length of
// pattern
p = (ALPHABET_SIZE * p + pattern.charAt(i)) % q;
t = (ALPHABET_SIZE * t + text.charAt(i)) % q;
 }

for (i = 0; i <= n - m; i++) {
// if the calculated hash value of the pattern and text matches then
// all the characters of the pattern is matched with the text of length equal to length
// of the pattern if all matches then pattern exist in string if not then the hash value
// of the first character of the text is subtracted and hash value of the next character
// after the end of the evaluated characters is added
if (p == t) {
// if hash value matches then the individual characters are matched
for (j = 0; j < m; j++) {
// if not matched then break out of the loop
if (text.charAt(i + j) != pattern.charAt(j)) {
break;
 }
 }

// if all characters are matched then pattern exist in the string
if (j == m) {
System.out.println("Pattern found at index " + i);
 }
 }

// if i<n-m then hash value of the first character of the text is subtracted and hash
// value of the next character after the end of the evaluated characters is added to get
// the hash value of the next window of characters in the text
if (i < n - m) {
t = (ALPHABET_SIZE * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;

// if hash value becomes less than zero than q is added to make it positive
if (t < 0) {
t = (t + q);
 }
 }
 }
 }
}