Pattern Guide
Z-Function & String Matching
"z[i] = length of longest string starting at i that matches a prefix. O(n) pattern matching."
The Z-function z[i] gives the length of the longest substring starting at position i that is also a prefix of the string. Z-function enables O(n + m) pattern matching (concatenate pattern + "$" + text, find z[i] = len(pattern)) and many string problems. Complements KMP: both solve the same problems but from different perspectives (Z uses explicit lengths, KMP uses failure links).
Problems you can solve with this pattern
4 problems · click any to start solving
// Compute Z-function in O(n)
function zFunction(s) {
const n = s.length, z = new Array(n).fill(0);
let l = 0, r = 0;
for (let i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z; // z[0] = 0 by convention
}
// Pattern matching: find all occurrences of pattern in text
function findAll(text, pattern) {
const s = pattern + '$' + text; // '$' must not appear in pattern/text
const z = zFunction(s);
const m = pattern.length, positions = [];
for (let i = m + 1; i < s.length; i++) {
if (z[i] === m) positions.push(i - m - 1); // position in text
}
return positions;
}
// Also useful:
// Number of times pattern appears as prefix of all suffixes = z values
// Minimum period of string: smallest p such that s[i] = s[i-p] for all i >= p
// Minimum period = n - z[n - z[n-1]] ... find with Z-functionZ-function is conceptually simpler than KMP. z[i] = length of longest string starting at i that matches a prefix of the whole string (z[0] = 0 by convention). Compute in O(n) using a window [l, r] that tracks the rightmost Z-box seen. If i < r, z[i] ≥ min(z[i-l], r-i+1), then extend manually. Pattern matching: form s = pattern + "$" + text. Any position where z[i] = len(pattern) is a match.
// Compute Z-function in O(n)
function zFunction(s) {
const n = s.length, z = new Array(n).fill(0);
let l = 0, r = 0;
for (let i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z; // z[0] = 0 by convention
}
// Pattern matching: find all occurrences of pattern in text
function findAll(text, pattern) {
const s = pattern + '$' + text; // '$' must not appear in pattern/text
const z = zFunction(s);
const m = pattern.length, positions = [];
for (let i = m + 1; i < s.length; i++) {
if (z[i] === m) positions.push(i - m - 1); // position in text
}
return positions;
}
// Also useful:
// Number of times pattern appears as prefix of all suffixes = z values
// Minimum period of string: smallest p such that s[i] = s[i-p] for all i >= p
// Minimum period = n - z[n - z[n-1]] ... find with Z-function- Both solve the same problems in O(n)
- Z: explicit "how far does this suffix match the prefix" — often more intuitive
- KMP: failure function "what's the longest proper prefix-suffix" — better for streaming
- Z is generally easier to implement and reason about
Key applications:
- Pattern matching in O(n + m): concat pattern + "#" + text, find z[i] = m
- Minimum string period: first i where z[i] = n-i and n%i = 0
- Palindrome queries: concat s + "#" + reverse(s)
- Count prefix occurrences: z[i] > 0 means position i extends a prefix match