Advanced String Algorithms: KMP, Rabin-Karp, Z-Algorithm
Concludes the 43-week curriculum with linear-time substring search: Knuth-Morris-Pratt (LPS array, $O(N+M)$), Rabin-Karp (Rolling Hash, $O(N+M)$ avg), Z-Algorithm ($O(N+M)$), and Manacher's Algorithm ($O(N)$).
What You'll Learn
- ✓Replace brute-force $O(N \times M)$ substring searches with linear-time $O(N + M)$ pattern matching.
- ✓Implement Knuth-Morris-Pratt (KMP) Algorithm: build Longest Prefix Suffix (LPS) table in $O(M)$ and match in $O(N)$ without text backtracking.
- ✓Implement Rabin-Karp Algorithm: Rolling Hash with modular arithmetic and hash collision resolution.
- ✓Implement Z-Algorithm: compute $Z$-array where $Z[i]$ is the length of longest common prefix starting at index $i$ in $O(N + M)$ time.
- ✓Understand Manacher's Algorithm for finding the Longest Palindromic Substring in linear $O(N)$ time.
Core Concepts
Linear Substring Search Paradigm
O(n + m)Finding occurrences of pattern string P (length m) within text string T (length n) in O(n + m) time.
KMP Longest Prefix Suffix (LPS)
O(m) preprocess, O(n) matchPrecomputing LPS array to shift pattern smartly upon mismatch without re-scanning matched text characters.
Rabin-Karp Rolling Hash
O(n + m) average, O(n * m) worstComputing hash values of sliding substrings in O(1) by removing leading character and adding trailing character.
Z-Algorithm & Z-Box Matching
O(n + m)Maintaining [L, R] segment boundaries to reuse previously matched character counts in O(n + m) total time.
Manacher's Palindrome Algorithm
O(n)Inserting sentinel characters and expanding around centers while tracking palindrome boundaries in O(n) time.
“It is not enough to be in the right place at the right time. You should also have an open mind at the right time.”
— Paul Erdos