Z-algorithm¶
For every position of a string, find how far the string starting there agrees with the start of the whole string. A "box" of already-known agreement lets most values be copied instead of recomputed, so the whole array takes linear time.
| Time | Extra space | Output |
|---|---|---|
| \(O(n)\) for a string of length \(n\); \(O(n + m)\) for matching | \(O(n)\) | the Z-array; every match position |
The idea¶
The Z-array of a string \(s\) is
For aabxaab: z = [7, 1, 0, 0, 3, 1, 0]. For example \(z[4] = 3\) because aab at position 4 matches the first
three letters, and then the string ends.
Pattern matching comes free: build the Z-array of pattern + separator + text, with a separator letter that
appears in neither. Every position in the text part with \(z \ge m\) is a match.
To compute it fast, keep the box \([l, r)\): the match with the prefix that reaches furthest to the right so far. The letters \(s[l..r)\) are a copy of \(s[0..r-l)\). So for a position \(i\) inside the box, the answer \(z[i - l]\) (already known, from the copy at the start) tells how far \(s[i..]\) agrees, at least up to the box edge \(r\). Only beyond \(r\) do letters need to be compared.
How it works¶
- \(z[0] = n\); \(l = r = 0\).
- For \(i = 1, 2, \dots\):
- If \(i < r\): start with \(z[i] = \min(r - i,\; z[i - l])\).
- Extend \(z[i]\) by comparing \(s[z[i]]\) with \(s[i + z[i]]\) while they are equal.
- If \(i + z[i] > r\), move the box: \(l = i\), \(r = i + z[i]\).
Code¶
def z_array(s):
"""z[i] = the length of the longest stretch starting at i that equals the start of s (z[0] = len(s))."""
n = len(s)
z = [0] * n
if n:
z[0] = n
l = r = 0 # s[l:r] is the rightmost stretch found that equals a prefix
for i in range(1, n):
if i < r: # inside a known stretch: reuse the value from the copy at the start
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]: # then try to extend by direct comparison
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
def z_search(text, p, sep="\0"):
"""Every position where p starts in text: z-values of p + separator + text that reach len(p)."""
z = z_array(p + sep + text)
m = len(p)
return [i - m - 1 for i in range(m + 1, len(z)) if z[i] >= m]
if __name__ == "__main__":
print(z_array("aabxaab"))
print(z_array("aaaaa"))
print(z_search("the red planet has red dust", "red"))
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ZAlgorithm {
/** z[i] = the length of the longest stretch starting at i that equals the start of s (z[0] = len(s)). */
static int[] zArray(String s) {
int n = s.length();
int[] z = new int[n];
if (n > 0) z[0] = n;
int l = 0, r = 0; // s[l..r) is the rightmost stretch found that equals a prefix
for (int i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]); // inside a known stretch: reuse the copy's value
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; // then extend directly
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}
/** Every position where p starts in text: z-values of p + separator + text that reach len(p). */
static List<Integer> zSearch(String text, String p) {
int[] z = zArray(p + "\0" + text);
int m = p.length();
List<Integer> found = new ArrayList<>();
for (int i = m + 1; i < z.length; i++) if (z[i] >= m) found.add(i - m - 1);
return found;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(zArray("aabxaab")));
System.out.println(Arrays.toString(zArray("aaaaa")));
System.out.println(zSearch("the red planet has red dust", "red"));
}
}
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// z[i] = the length of the longest stretch starting at i that equals the start of s (z[0] = len(s)).
vector<int> zArray(const string& s) {
int n = s.size();
vector<int> z(n, 0);
if (n > 0) z[0] = n;
int l = 0, r = 0; // s[l..r) is the rightmost stretch found that equals a prefix
for (int i = 1; i < n; i++) {
if (i < r) z[i] = min(r - i, z[i - l]); // inside a known stretch: reuse the value from the copy
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; // then try to extend by direct comparison
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}
// Every position where p starts in text: z-values of p + separator + text that reach len(p).
vector<int> zSearch(const string& text, const string& p) {
vector<int> z = zArray(p + string(1, '\0') + text);
int m = p.size();
vector<int> found;
for (int i = m + 1; i < (int)z.size(); i++) if (z[i] >= m) found.push_back(i - m - 1);
return found;
}
string show(const vector<int>& v) {
string s = "[";
for (size_t i = 0; i < v.size(); i++) s += (i ? ", " : "") + to_string(v[i]);
return s + "]";
}
int main() {
cout << show(zArray("aabxaab")) << "\n" << show(zArray("aaaaa")) << "\n";
cout << show(zSearch("the red planet has red dust", "red")) << "\n";
}
Output: [7, 1, 0, 0, 3, 1, 0], [5, 4, 3, 2, 1] for aaaaa, and [4, 19]: the two places red appears in
the red planet has red dust.
When to use it¶
- Pattern matching with a short, easy-to-remember algorithm (one function, one loop).
- Periods and repeats: \(s\) has period \(p\) exactly when \(z[p] = n - p\) (or \(p = n\)).
- Counting distinct substrings, compressing strings, finding the longest prefix that is also a suffix and many other contest-style string problems.
- Wherever KMP's prefix function is used: the two arrays can be converted into each other in \(O(n)\).
Common mistakes¶
- A separator that occurs in the text or pattern: matches would run across it. The code uses the zero character; with arbitrary bytes, compute the Z-array of the pattern and scan the text separately instead.
- Forgetting the cap \(r - i\): the copy is only known to agree up to the box edge.
- Not moving the box when a longer match is found, which breaks the linear time.
- The value of \(z[0]\): some books set it to 0, others to \(n\); make sure the rest of the code agrees.
Going deeper¶
Each part below starts closed; open the ones you want.
Sample walkthrough: aabxaabxaa
| \(i\) | inside the box? | start value | compared letters | \(z[i]\) | box after |
|---|---|---|---|---|---|
| 1 | no | 0 | a=a, then b≠a |
1 | [1, 2) |
| 2 | no | 0 | b≠a |
0 | [1, 2) |
| 3 | no | 0 | x≠a |
0 | [3, 3) (empty) |
| 4 | no | 0 | aabxaa matches, then the string ends |
6 | [4, 10) |
| 5 | yes, copy of 1 | min(5, z[1] = 1) = 1 | b≠a |
1 | [4, 10) |
| 6 | yes, copy of 2 | min(4, 0) = 0 | b≠a |
0 | [4, 10) |
| 7 | yes, copy of 3 | min(3, 0) = 0 | x≠a |
0 | [4, 10) |
| 8 | yes, copy of 4 | min(2, z[4] = 6) = 2 | none: the string ends | 2 | [4, 10) |
| 9 | yes, copy of 5 | min(1, 1) = 1 | none: the string ends | 1 | [4, 10) |
Result: [10, 1, 0, 0, 6, 1, 0, 0, 2, 1]. At \(i = 8\) the copy said 6, but only 2 letters remain inside the box,
which is why the value is capped.
The math: correctness and the linear bound
The copy is valid. By the choice of the box, \(s[l..r) = s[0..r-l)\). For \(l < i < r\), the letters \(s[i..r)\) equal \(s[i-l..r-l)\). So \(s[i..]\) and \(s[0..]\) agree for exactly \(\min(z[i-l],\, r - i)\) letters within the box:
- if \(z[i-l] < r - i\), the disagreement happens inside the box, so \(z[i] = z[i-l]\) exactly and no comparison will succeed;
- otherwise \(z[i] \ge r - i\), and the comparisons continue from \(r\).
Linear time. Every successful comparison at position \(i\) looks at the letter \(s[i + z[i]]\) with \(i + z[i] \ge r\), and afterwards the box edge \(r\) moves past it. So \(r\) grows by one per successful comparison, and \(r \le n\): at most \(n\) successful comparisons in total. Each \(i\) makes at most one failed comparison. Total \(O(n)\).
From Z to π. For each \(i\) with \(z[i] > 0\), the positions \(i, \dots, i + z[i] - 1\) end borders; setting \(\pi[i + z[i] - 1] \ge z[i]\) and propagating gives the prefix function in \(O(n)\).
Watch it step by step
Blue is the box \([l, r)\), faded blue is the copy at the start, orange letters are being compared, and red is the \(z\) value being found.
Variations and related ideas
- Manacher's algorithm uses the same "box" idea to find all palindromes around every centre in \(O(n)\).
- Suffix arrays and suffix trees answer far more questions (any substring, longest repeated substring) in \(O(n \log n)\) or \(O(n)\) to build.
- Gusfield's book presents the Z-algorithm as the "fundamental preprocessing" and builds Boyer–Moore and other matchers on top of it.
See also¶
References¶
- D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, Chapter 1.
- M. G. Main and R. J. Lorentz, "An O(n log n) algorithm for finding all repetitions in a string", Journal of Algorithms 5(3), 1984 (an early use of the same preprocessing).