Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Introduction to Rabin-Karp Algorithm
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment