Z-Function
Measure how much each suffix matches the full string, then reuse that linear-time structure for pattern matching and periodicity.
Z-Function
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The Z-function stores, for every position \(i\), the length of the longest prefix of the string that matches the suffix starting at \(i\). It is one of the cleanest linear-time string tools because its meaning is direct: ``how much does the whole string match here?''
When to Use It
Use the Z-function when:
you need pattern matching on \(p + \# + t\),
the problem asks about borders, repetitions, or periodicity,
you want a prefix-matching tool that is often easier to reason about than KMP for some tasks.
Core Idea
Let \(z[i]\) be the longest common prefix of \(s\) and \(s[i \dots]\). The naive computation is quadratic, but the linear algorithm keeps the rightmost matched segment \([l, r]\) and reuses previous information inside that window.
Key Insight
Inside the current matched segment, the string already mirrors the prefix. That lets me copy part of a previous answer instead of comparing from scratch, and only extend when necessary.
Operations / Main Technique
compute the Z-array in one scan,
pattern matching by running Z on \(p + \# + t\),
detect periods or borders from large Z-values.
Worked example.
For \(\texttt{s = "aaaaa"}\), the Z-array is \([0, 4, 3, 2, 1]\). Every suffix is a prefix again, just shorter.
Correctness Intuition
The maintained window \([l, r]\) is a segment known to match the prefix. If \(i\) lies inside it, the corresponding prefix position already tells me a lower bound for \(z[i]\). Any extra matching beyond that lower bound is found by explicit extension. No character comparison is wasted too many times, which gives linear time.
Complexity Analysis
The Z-function is computed in \(O(n)\) time and \(O(n)\) memory.
Implementation
The code provides the standard linear routine and one helper that returns all pattern-occurrence positions inside a text using the concatenation trick.
Common Pitfalls
Forgetting to use a separator that cannot appear in the original strings.
Misreading \(z[i]\) as a substring-substring LCP instead of prefix-suffix LCP.
Confusing the Z-function with the prefix function from KMP.
Variants / Extensions
Border and periodicity checks.
String compression problems using smallest period detection.
Comparison with KMP: same asymptotic power, different viewpoint.
Practice Problems
Find all occurrences of a pattern in a text.
Determine the smallest period of a string.
Count borders or repeated prefix occurrences.
References
Code
Contest-ready reference implementation for the idea explained above.
vector<int> z_function(const string& s) {
int n = (int)s.size();
vector<int> z(n, 0);
for (int i = 1, l = 0, r = 0; 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;
}
vector<int> find_occurrences_z(const string& pattern, const string& text) {
string merged = pattern + "#" + text;
vector<int> z = z_function(merged);
vector<int> positions;
int m = (int)pattern.size();
for (int i = m + 1; i < (int)merged.size(); ++i) {
if (z[i] >= m) {
positions.push_back(i - m - 1);
}
}
return positions;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.