chtefi
9/26/2015 - 9:56 PM

## Search the occurences of a substring in a string | Karp-Rabin algorithm

Search the occurences of a substring in a string | Karp-Rabin algorithm

``````// TODO : implement multi patterns finding (where the KR algo really shines)
// otherwise a simple and native indexOf(...) should be faster right ?

const KR = function(str, pattern, cb) {
const n = str.length;
const m = pattern.length;

// bit at pattern.length-1 set to 1
// we are going to use it when rolling hash
let d = Math.pow(2, m - 1);

const rollingHash = (previous, next, hash) => ((hash - previous.charCodeAt(0)*d) << 1) + next.charCodeAt(0);

let hstr = 0;
let hpattern = 0;
for (let i = 0; i < m; i++) {
hstr = (hstr << 1) + str.charCodeAt(i);
hpattern = (hpattern << 1) + pattern.charCodeAt(i);
}

// Searching
for (let j = 0; ; j++) {
if (hstr === hpattern) {
if (str.substring(j, j+m) === pattern.substring(0, m)) {
cb(j)
} else {
console.log('false positive at ', j);
}
}

// end of the string
if (j + m === n) {
break;
}

hstr = rollingHash(str[j], str[j + m], hstr);
}

};``````