Expert · Module 28 · Lesson 3 of 4
Linear-Time String Matching: Z-Algorithm, Manacher's, and Aho-Corasick
Compute longest common prefixes for every suffix in O(N) time using the Z-Algorithm's [L, R] Z-box invariant, find all palindromic substrings in O(N) with Manacher's mirror box, and match dictionaries with Aho-Corasick.
By the end you can
- Compute the Z-array (z[i] = LCP of S and S[i..]) in O(N) time by reusing matches inside the rightmost Z-box [L, R]
- Apply the Z-array on 'P + # + T' to find all occurrences of pattern P in text T in O(|P| + |T|) time and O(|P|) space
- Understand how Manacher's palindrome mirror and Aho-Corasick trie failure links generalize the exact same prefix/box reuse invariant
Builds on Rolling hash and Rabin-Karp, KMP and prefix functions, Tries.
01 · A question first
Given a string S of length 1,000,000, computing the longest common prefix between S and every suffix S[i..] naively takes 500 billion comparisons. How does keeping track of a single interval [L, R]—the rightmost matched 'Z-box'—compute all 1,000,000 values in linear O(N) time?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Intuitive Explanation & Real-World Analogy
- Core Concepts & Visual Walkthrough
- Pseudocode
- Multi-Language Implementations (C++, Java, Python)
- Time & Auxiliary Space Complexity Derivation
- Edge Cases & Common Beginner Mistakes
- Alternative Approaches (Brute Force vs. Optimal)
- Pattern Recognition Guide & Three-Stage Practice Plan
03 · Practice
Something wrong with this lesson? Report a problem