String Algorithms: Hashing and KMP
Polynomial hashes for comparing substrings in O(1) and the prefix function (KMP) for pattern search.
Comparing substrings character by character costs O(n) per comparison. Two tools remove that limitation.
The polynomial hash: a string maps to the number h = s[0]·p^(k-1) + s[1]·p^(k-2) + ... modulo some prime. Having precomputed prefix hashes and the powers of p, the hash of ANY substring comes out in O(1) — and equal substrings have equal hashes. Different substrings can theoretically collide, but with a modulus around 10⁹ the probability is negligible, and for the paranoid there is double hashing.
Comparing substrings with hashes. Enter: abacaba 2, then "l1 r1 l2 r2" queries: 1 3 5 7 and 1 2 2 3
On the example: the substrings [1,3] and [5,7] of abacaba are both "aba" (YES), while [1,2] and [2,3] are "ab" and "ba" (NO).
The second tool is the prefix function: pi[i] is the length of the longest proper prefix of the string that is also its suffix at position i. It is computed in O(n) and underlies the KMP algorithm: to find a pattern in a text, concatenate "pattern # text" and look for positions where pi equals the pattern length.
KMP: all occurrences of the pattern. Enter: ababcab ab
On the example the pattern ab occurs in ababcab at positions 1, 3 and 6.
The heart of the algorithm is the while loop j = pi[j-1]: on a mismatch we don't start over but fall back to the next candidate prefix. In total, the pointer j decreases no more than it increases — hence O(n).
Task: use the prefix function to find the smallest period of a string (hint: n - pi[n-1], provided n is divisible by that value).
Mark the lesson as completed.