Polynomial Hashing — String Hash for Fast Comparison

Why it matters

Polynomial hashing enables many O(n) string algorithms.

The architecture

Hash: polynomial in prime p mod prime q.

Rolling: shift left = multiply p; add new char.

How it works end to end

Collision: single hash has probability 1/q. Double hash: 1/q².

Substring comparison: hash both, compare.

Applications: substring search, longest common substring.