Z Algorithm from Scratch (2026)
The Z Algorithm computes the Z-array for a string in O(n) time, where Z[i] is the length of the longest substring starting at position i that matches the string's prefix. It enables linear-time pattern matching without hashing.
Z-array construction uses a window [l, r] that tracks the rightmost prefix match, leveraging previously computed values to avoid redundant character comparisons.
Z-Array Construction
The algorithm maintains the interval [l, r] of the rightmost prefix match. For a new position i within [l, r], Z[i] is initialized from Z[i-l] but capped at r-i+1. If the initial value extends beyond r, characters are compared explicitly.
This window maintenance guarantees O(n) total character comparisons, as r only moves forward.
vector computeZArray(string& s) {
int n = s.size(), l = 0, r = 0;
vector Z(n, 0);
for (int i = 1; i < n; i++) {
if (i <= r)
Z[i] = min(r - i + 1, Z[i - l]);
while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])
Z[i]++;
if (i + Z[i] - 1 > r)
l = i, r = i + Z[i] - 1;
}
return Z;
} Pattern Matching with Z Algorithm
To find pattern occurrences in text, concatenate pattern + '$' + text and compute the Z-array of this combined string. Any position i where Z[i] == pattern length indicates a match starting at i - pattern.length - 1 in the text.
The separator character must not appear in either pattern or text to ensure Z values stop at boundaries correctly.
vector zPatternMatch(string& text, string& pattern) {
string combined = pattern + '$' + text;
vector Z = computeZArray(combined);
int m = pattern.size();
vector matches;
for (int i = m + 1; i < combined.size(); i++)
if (Z[i] == m) matches.push_back(i - m - 1);
return matches;
} Frequently Asked Questions
What is the Z-array?
Z[i] stores the length of the longest substring starting at index i that matches the prefix of the string. Z[0] is typically defined as 0 since the entire string trivially matches itself at position 0.
How does Z Algorithm compare to KMP?
Both achieve O(n+m) pattern matching. Z Algorithm is often simpler to implement and understand, while KMP operates in-place on the text without requiring concatenation and extra memory.
Originally published on Ayodhyyya. Last updated June 1, 2026.