The Karp-Rabin Fingerprint Method

Definition: Tr = T[r .. r+n-1]

Definition: H(S) = S(n) + 2*S(n-1) + 4*S(n-2) + ... + 2n-1*S(1)

Idea: Find occurrences of P in T by checking whether H(P) = H(Tr)

Problem: Calculating H(P) is linear in n (the length of P)

Solution: Use Hp(P) = H(P) mod p as a fingerprint of P

(This may result in false positives, which can either be eliminated by checking, or the probability of false positives can be bounded by picking p appropriately and using multiple moduli.)

Hp(Tr) can be calculated from Hp(Tr-1) by the equation

Hp(Tr) = [ 2*Hp(Tr-1) - (2n mod p) * T(r-1) + T(r+n-1) ] mod p