Skip to content

Instantly share code, notes, and snippets.

@amasad
Created May 14, 2011 18:03
Show Gist options
  • Save amasad/972457 to your computer and use it in GitHub Desktop.
Save amasad/972457 to your computer and use it in GitHub Desktop.
Rabin Karp in JS
//RABIN KARP
var BASE = 256,
PRIME = 256199087;
function tonum(c){
return c.charCodeAt(0);
}
function mod(a, p, m){
if (p == 0) return 1;
var sqr = mod(a, p/2, m) % m;
sqr = (sqr * sqr) % m;
if (p & 1) return ((a % m) * sqr) % m;
else return sqr;
}
function rabinHash(P){
var p = 0, m = P.length,
i,
q = PRIME, d = BASE;
for (i=0; i < m; i++)
{
p = (d*p + tonum(P[i])) % q;
}
return p;
}
exports.rabinHash = rabinHash;
function rabinMatch(T, P){
var i,j,p,t,n,m,h,found,
d = BASE, q = PRIME;
n = T.length - 1;
m = P.length - 1;
h = mod(d,m - 1,q);
p = t = 0;
for (i=0; i<m; i++)
{
p = (d*p + tonum(P[i])) % q;
t = (d*t + tonum(T[i])) % q;
}
for (i=0; i<=n-m; i++)
{
if (p == t)
{
found = 1;
for (j=0; j<m; j++)
if (P[j] != T[i+j])
{
found = 0;
break;
}
if (found) return i;
} else {
t = (d*(t - ((tonum(T[i])*h) % q)) +
tonum(T[i+m])) % q;
}
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment