What is the Z-Algorithm for String Matching?
Learn how the Z-algorithm builds the Z-array for O(n) pattern matching, with code and interview guidance.
Expected Interview Answer
The Z-algorithm computes, for every position in a string, the length of the longest substring starting there that also matches a prefix of the whole string, building this Z-array in O(n) time by reusing overlap information from a previously computed Z-box instead of comparing from scratch at every position.
To use it for pattern matching, you concatenate pattern + separator + text (where the separator appears nowhere in either) and compute the Z-array of the combined string; any position in the text portion where the Z-value equals the pattern's length marks a full match. The efficiency comes from maintaining a 'Z-box' — the interval [l, r] of the rightmost match extending furthest right found so far — and when computing Z at a new position inside that box, its value can be initialized from the corresponding earlier position inside the prefix match, clamped to not exceed the box's remaining length, only falling back to direct character comparison when that bound is reached. Every character comparison either extends the current rightmost box or is skipped because it's already covered by a previous box, which is what bounds the total work to O(n). The Z-algorithm is functionally similar to KMP for exact matching but the Z-array itself is a more general and reusable tool, showing up directly in problems about string periodicity and prefix-function-based counting.
- O(n + m) pattern matching via a single Z-array computation
- Z-box reuse avoids re-comparing already-verified overlaps
- Generalizes beyond matching to periodicity and prefix-count problems
- Conceptually simpler prefix semantics than the KMP failure function
AI Mentor Explanation
The Z-algorithm is like a coach checking, from every ball of a long highlights reel, how much of the opening over's exact sequence repeats starting right there, reusing earlier findings instead of comparing from scratch at each ball. The coach keeps track of the furthest-reaching match found so far, called the active window, and if the current ball falls inside that window, its answer can start from the already-known value at the mirrored ball near the start of the reel, capped by how much window remains. Only when that cap is reached does the coach actually compare balls one by one going forward, and every such comparison either extends the active window or was already accounted for. This is why scanning the whole reel for repeats of the opening sequence takes time proportional to the reel's length, not the square of it.
Step-by-Step Explanation
Step 1
Concatenate pattern, separator, and text
Build pattern + sep + text where sep occurs in neither string, so matches never cross the boundary.
Step 2
Initialize the Z-box
Track [l, r], the interval of the rightmost prefix-match found so far during the scan.
Step 3
Reuse or expand at each position
Inside the box, seed Z[i] from Z[i-l] clamped to r-i+1; outside or at the cap, expand by direct comparison.
Step 4
Scan the text portion for matches
Any position in the text segment where Z equals the pattern's length marks a full match; report its offset.
What Interviewer Expects
- Define the Z-array precisely: Z[i] is the longest common prefix of the string with its suffix starting at i
- Explain the Z-box reuse rule and its clamp condition
- State the O(n) amortized bound and why comparisons never redo covered work
- Describe the concatenation trick for using Z-array to do pattern matching, including the separator requirement
Common Mistakes
- Forgetting to clamp the reused Z-value to the remaining box length before expanding
- Omitting or reusing a separator that actually appears in the text or pattern
- Confusing Z[i] with the KMP LPS array, which measures a different prefix-suffix relationship
- Not resetting or updating [l, r] correctly, causing values to be seeded from a stale box
Best Answer (HR Friendly)
“The Z-algorithm builds an array that tells you, at every position in a string, how far that spot matches the very beginning of the string, and it does this in linear time by reusing earlier comparisons. I'd use it for pattern matching by joining the pattern and text with a separator, since it's a clean, general-purpose tool beyond just search, useful for things like string periodicity.”
Code Example
def z_array(s):
n = len(s)
z = [0] * n
z[0] = n
l, r = 0, 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
def z_search(text, pattern):
combined = pattern + "$" + text
z = z_array(combined)
m = len(pattern)
matches = []
for i in range(m + 1, len(combined)):
if z[i] == m:
matches.append(i - m - 1)
return matchesFollow-up Questions
- How would you use the Z-array to find the shortest period of a string?
- How does the Z-algorithm differ conceptually from the KMP failure function?
- Why must the separator character not appear in either the pattern or the text?
- How would you count occurrences of each prefix as a substring using the Z-array?
MCQ Practice
1. What does Z[i] represent in the Z-array of a string s?
Z[i] measures how far the substring starting at i matches the beginning of the whole string.
2. What is the time complexity of building the Z-array for a string of length n?
The Z-box reuse ensures each character comparison either extends the rightmost box or is skipped, bounding work to O(n).
3. How do you use the Z-array to search for a pattern in a text?
A Z-value equal to the pattern length in the text portion means that position starts a full match of the pattern.
Flash Cards
What does the Z-array store at index i? — The length of the longest prefix of the string that matches the substring starting at i.
What is the time complexity of Z-array construction? — O(n), using the Z-box reuse technique.
How do you adapt the Z-algorithm for pattern matching? — Concatenate pattern + separator + text, then look for Z-values equal to the pattern's length in the text portion.
What must the separator character satisfy? — It must not appear anywhere in either the pattern or the text, to prevent cross-boundary matches.