**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^{n}
mod p) * T(r-1) + T(r+n-1) ] mod p