Introduction to Rabin-Karp Algorithm

RabinKarp.java

public class RabinKarp {

    public static final int NOT_FOUND_INDEX = -1;
    public static final int PRIME = 7;

    public static void main(String args[]){
        System.out.println("**************** Rabin Karp *****************");

        String text = "abcabac";
        String pattern = "abac";
        long initialTime = System.nanoTime();
        int index = findPatternInText(pattern, text);
        long finalTime = System.nanoTime();
        if(index == NOT_FOUND_INDEX)
            System.out.println("Pattern is not find in the text");
        else
            System.out.println("Successful! Pattern found at index "+index);

        System.out.println("Time taken for matching "+(finalTime - initialTime));
    }

    private static int findPatternInText(String pattern, String text) {
        Integer patternHash = getHash(pattern);
        char[] textArray = text.toCharArray();
        int textLength = textArray.length;
        int patternLength = pattern.length();
        char[] patternArray = pattern.toCharArray();
        int matchedIndex = NOT_FOUND_INDEX;
        Integer textHash = 0;
        for(int i = 0; i < textLength; i++){
            if(i < patternLength){
                textHash = textHash + textArray[i] * Double.valueOf(Math.pow(PRIME, i)).intValue();
            } else {
                textHash = textHash - textArray[i - patternLength];
                textHash = textHash / 11;
                textHash = textHash + textArray[i] * Double.valueOf(Math.pow(PRIME,patternLength - 1)).intValue();
            }

            boolean isMatchingVerified = false;
            if(i == (patternLength - 1)){
                if(textHash == patternHash) {
                    isMatchingVerified = verifyString(textArray, patternArray, 0, patternLength);
                    if(isMatchingVerified)
                        matchedIndex = 0;
                }
            }

            if(i > (patternLength - 1)){
                isMatchingVerified = verifyString(textArray, patternArray, i - patternLength + 1, i);
                if(isMatchingVerified)
                    matchedIndex = i - patternLength + 1;
            }
        }
        return matchedIndex;
    }

    private static boolean verifyString(char[] textArray, char[] patternArray, int start, int end) {
        boolean isMatchingVerified = true;
        for(int i = start, j = 0; i <= end; i++, j++ ){
            if(textArray[i] != patternArray[j])
                isMatchingVerified = false;
        }
        return isMatchingVerified;
    }

    private static Integer getHash(String string) {
        char[] stringArray = string.toCharArray();
        Integer patternHash = 0;
        int patternLength = stringArray.length;
        for(int i = 0; i < patternLength; i++){
            patternHash = patternHash + stringArray[i] * Double.valueOf(Math.pow(PRIME, i)).intValue();
        }
        return patternHash;
    }
}