Knuth-Morris-Pratt (KMP) Algorithm
Key Insight
After a partial match fails, the prefix function tells us how far to shift the pattern without re-comparing characters we already know match. The text pointer never moves backward.
Prefix Function (Failure Function)
pi[i] = length of the longest proper prefix of P[0..i] that is also a suffix.
Example: Pattern "ABABACA" -> pi = [0, 0, 1, 2, 3, 0, 1]
Build Prefix Table — O(n)
def build_prefix(pattern: str) -> list[int]:
[Description truncada. Veja o README completo no GitHub.]