Stage 1 · Code
String Algorithms
Z Algorithm
See how the Z-array measures prefix matches at every position and how the `[L, R]` box lets later positions inherit work instead of recomputing it.
Why Recomputing Prefixes Is Expensive
Imagine asking the same question at every position in a string: 'How many characters from here match the beginning of the whole string?' The naive solution starts a fresh comparison each time. That can be quadratic because long repeated prefixes make neighboring positions redo almost the same work.
The Z algorithm stores the answer to exactly that question in an array Z, where Z[i] is the length of the longest substring starting at i that matches the prefix of the string. Once you think of substring search as a repeated prefix-comparison problem, the Z array becomes a natural alternative to KMP.
KMP asks how the pattern overlaps with itself at the end of a prefix. Z asks how the prefix reappears starting at each position. They encode different views of the same reuse idea.
What Z Values Mean
Take the string aabcaabxaaaz. At index 4, the suffix begins with aabx..., which matches the global prefix aab... for three characters, so Z[4] = 3. At index 8, the suffix begins with aaaz, which matches the prefix aab... for two characters, so Z[8] = 2. A zero means the first character already disagrees with the string's first character.
string: a a b c a a b x a a a z
index : 0 1 2 3 4 5 6 7 8 9 10 11
Z : 0 1 0 0 3 1 0 0 2 2 1 0
Interpretation:
- Z[4] = 3 because substring 'aab...' matches prefix 'aab...'
- Z[9] = 2 because substring 'aaz' matches prefix 'aa' for two steps
- Z[3] = 0 because 'c' does not match the first character 'a'Some references set Z[0] = n; others set it to 0 by convention because the whole string trivially matches itself. Either choice is fine as long as the rest of the logic stays consistent.
Building the Z Box
The linear-time trick is to maintain the rightmost interval [L, R] whose substring is known to match the prefix. This interval is called the Z box. If the next position i lies outside the box, you must compare from scratch. But if i lies inside it, then a mirrored position k = i - L inside the prefix already tells you something about Z[i].
There are two cases. If Z[k] is strictly smaller than the remaining box length R - i + 1, you can copy that value directly because the known box already proves it. If Z[k] reaches or exceeds the box boundary, you know at least R - i + 1 characters match, and only then do you continue comparing past R to see whether the match extends further.
Current Z box for 'aabcaabxaaaz' after processing index 8:
L = 8, R = 9 because substring s[8..9] = 'aa' matches prefix s[0..1] = 'aa'
Now i = 9 lies inside [L, R]
k = i - L = 1
Z[1] = 1 and remaining box length is 1
=> we may already claim one matching character
=> then compare beyond R to see if the match grows
=> s[10] = 'a' still matches prefix[1] = 'a'
=> Z[9] becomes 2The Z box does not magically answer everything. It answers as much as the existing proof allows, then hands control back to explicit comparison only when necessary.
| Situation | What Z does | Why it is safe |
|---|---|---|
i outside the current box | Compare from scratch | No earlier prefix proof covers this position |
i inside and Z[k] stays inside the box | Copy Z[k] | The known prefix match already certifies those characters |
i inside and Z[k] reaches the boundary | Start from the boundary and extend | Only characters beyond the proven region remain unknown |
Pattern Matching with Z
To search for a pattern P in text T, build the string P + '#' + T, where # is a separator that does not occur in either input. Any position in the combined string whose Z value equals len(P) marks a full prefix match of P, which means the pattern appears in the text at that aligned location.
pattern = aabx
text = zzzaabxaabx
combined = aabx#zzzaabxaabx
Whenever Z[i] = 4 in the combined string, the pattern matches there.
Those hits occur at the text positions where the substring starts with 'aabx'.The separator is important. It prevents a match from blending characters from the pattern side and the text side into one fake prefix match.
Go Implementation
The implementation below follows the standard [L, R] pattern closely. buildZ computes the array, and ZSearch wraps the pattern-matching trick by scanning the combined string for positions whose Z value reaches the full pattern length.
Practice Problems
Quiz
What does `Z[i]` store?
Summary
- The Z array stores prefix-match lengths for every starting position in a string.
- A rightmost
[L, R]match box lets the algorithm inherit previously proved comparisons and stay linear. - The Z view is especially elegant for pattern search via
pattern + separator + text. - Many border and repetition problems can be solved with either KMP or Z; the best choice is often whichever view feels more natural to you.
- If you understand why inherited values are safe inside the Z box, you understand the heart of the algorithm.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.