RabinKarpAlgorithm.java

package com.thealgorithms.searches;

// Implementation of Rabin Karp Algorithm

public final class RabinKarpAlgorithm {
    private RabinKarpAlgorithm() {
    }

    private static final int ALPHABET_SIZE = 256;

    public static int search(String pattern, String text, int primeNumber) {

        int index = -1; // -1 here represents not found
        int patternLength = pattern.length();
        int textLength = text.length();
        int hashForPattern = 0;
        int hashForText = 0;
        int h = 1;

        // The value of h would be "pow(d, patternLength-1)%primeNumber"
        for (int i = 0; i < patternLength - 1; i++) {
            h = (h * ALPHABET_SIZE) % primeNumber;
        }

        // Calculate the hash value of pattern and first
        // window of text
        for (int i = 0; i < patternLength; i++) {
            hashForPattern = (ALPHABET_SIZE * hashForPattern + pattern.charAt(i)) % primeNumber;
            hashForText = (ALPHABET_SIZE * hashForText + text.charAt(i)) % primeNumber;
        }

        // Slide the pattern over text one by one
        for (int i = 0; i <= textLength - patternLength; i++) {
            /* Check the hash values of current window of text
               and pattern. If the hash values match then only
               check for characters one by one*/

            int j = 0;
            if (hashForPattern == hashForText) {
                /* Check for characters one by one */
                for (j = 0; j < patternLength; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        break;
                    }
                }

                // if hashForPattern == hashForText and pattern[0...patternLength-1] = text[i, i+1, ...i+patternLength-1]
                if (j == patternLength) {
                    index = i;
                    return index;
                }
            }

            // Calculate hash value for next window of text: Remove
            // leading digit, add trailing digit
            if (i < textLength - patternLength) {
                hashForText = (ALPHABET_SIZE * (hashForText - text.charAt(i) * h) + text.charAt(i + patternLength)) % primeNumber;

                // handling negative hashForText
                if (hashForText < 0) {
                    hashForText = (hashForText + primeNumber);
                }
            }
        }
        return index; // return -1 if pattern does not found
    }
}
// This code is contributed by nuclode