rabin.js

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;
}

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;
	
}