The Karp-Rabin Fingerprint Method

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

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

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

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

Solution: Use H_p(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.)

H_p(T_r) can be calculated from H_p(T_r-1) by the equation

H_p(T_r) = [ 2*H_p(T_r-1) - (2ⁿ mod p) * T(r-1) + T(r+n-1) ] mod p