CONCEPT · International Master
KMP prefix function
also Knuth-Morris-Pratt · pi function · borders
π[i] is the longest proper border of the prefix s[0..i]. Matching and period checks become linear. Deterministic — no hash collisions.
Intuition
When a mismatch happens you already know how much of the pattern is still a live border. Jump there; do not slide by one.
When to reach for it
- CSES String Matching / Finding Borders / Finding Periods
- Single-pattern search at n=1e6
- Period of a string via n - π[n-1]
Usual pits
- Concatenating pattern+text without a separator
- Thinking the inner while is quadratic — it is amortized linear
- Using KMP when a hash would do and n is small — not wrong, just longer