Problem Statement: Given two strings a and b, find the position of a in b if a is a substring of b.
Solution: RabinKarp finds a position of a string (needle ) in another string (haystack). It aims to improve the search performance by using hashing. First hash of needle is calculated and then hash of haystack of same length as needle is calculated. Then if hash of needle matches the hash of prefix then character by character match is performed on needle and the prefix if the match is successful the we return the position. On the otherhand if hashes do not match then a charcter is removed from the prefix and new character is added from haystack and hash is recalculated and match is performed again.
Rabin Karp String Search217 views
function rabinKarpFind(needle,haystack){
// simple rolling hash function, just sums up all ascii values
function hash(x){
var hs=0;
for(var i=0;i<x.length;i++){
hs = hs+x.charCodeAt(i);
}
return hs;
}
// updates the hash by removing old char and adding new char
function updateHash(oldChar,newChar,oldHash){
return oldHash-oldChar.charCodeAt(0)+newChar.charCodeAt(0);
}
// matches string of equal length, returns true if they are equal
function matchStr(a,b){
var i;
if(a.length!=b.length){
return false;
}
for(i=0;i<a.length;i++){
if(a[i]!=b[i]){
return false;
}
}
return true;
}
var hs1 = hash(needle),
// this will be rolling hash
hs2 = hash(haystack.substring(0,needle.length)),
i;
for(i=0;i<haystack.length-needle.length+1;i++){
if(hs1==hs2){ // only if hashes are equal we need to do full match
if(matchStr(needle,haystack.substring(i,i+needle.length))){
return i;
}
}
if(haystack[i+needle.length]){
hs2 = updateHash(haystack[i],haystack[i+needle.length],hs2);
}
}
return -1;
}