Z Algorithm
The Z algorithm computes, for every position, how many characters match the string prefix and reuses the rightmost known match to run in linear time.
The Z array
For string S, Z[i] is the longest length such that S[0..Z[i]−1] equals S[i..i+Z[i]−1]. Z[0] is conventionally zero or N; choose and document one. The array exposes borders, repetitions, and prefix occurrences in a single scan.
A naive expansion from every i can compare repeated characters quadratically. The linear algorithm remembers the prefix match whose right boundary is farthest right and copies information from its mirrored prefix position before doing new comparisons.
- Each value compares a suffix with the prefix
- Z[0] needs a convention
- Naive independent expansion is quadratic
The rightmost Z-box
Maintain [L,R) with S[L..R−1]=S[0..R−L−1]. If i≥R, start Z[i]=0. If i<R, initialize Z[i]=min(R−i,Z[i−L]); the cap prevents claiming characters beyond the verified box.
Then compare S[Z[i]] with S[i+Z[i]] while in bounds. If i+Z[i] extends beyond R, replace the box. Values copied wholly inside the box need no new character comparisons.
- Boxes are half-open
- Mirror index is i−L
- Cap copied length at R−i
Terms, operations, and practical uses
Z values
- Z arrayZ array is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Prefix matchPrefix match is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Z-boxZ-box is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Linear scan
- Left boundary LLeft boundary L is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Right boundary RRight boundary R is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Mirror indexMirror index is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Matching
- SeparatorSeparator is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Pattern occurrencePattern occurrence is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Overlapping matchOverlapping match is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Build the Z array with a rightmost box
s="abacaba";n=len(s);z=[0]*n;l=r=0
for i in range(1,n):
if i<r:z[i]=min(r-i,z[i-l])
while i+z[i]<n and s[z[i]]==s[i+z[i]]:z[i]+=1
if i+z[i]>r:l,r=i,i+z[i]
print("Z:",", ".join(map(str,z)))#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
string s="abacaba";
vector<int> z(s.size());
int l=0,r=0;
for(int i=1;i<(int)s.size();i++) {
if(i<r) z[i]=min(r-i,z[i-l]);
while(i+z[i]<(int)s.size()&&s[z[i]]==s[i+z[i]]) z[i]++;
if(i+z[i]>r) l=i,r=i+z[i];
}
cout << "Z:";
for(int x:z) cout << ' ' << x;
cout << '\n';
}class Main {
public static void main(String[] args) {
String s="abacaba";
int[] z=new int[s.length()];
int l=0,r=0;
for(int i=1;i<s.length();i++) {
if(i<r) z[i]=Math.min(r-i,z[i-l]);
while(i+z[i]<s.length()&&s.charAt(z[i])==s.charAt(i+z[i])) z[i]++;
if(i+z[i]>r) {
l=i;
r=i+z[i];
}
}
StringBuilder out=new StringBuilder("Z:");
for(int x:z) out.append(' ').append(x);
System.out.println(out);
}
}Step through it
Running on abacaba
Why total work is linear
The inner comparison loop seems nested, but every successful comparison that was not copied advances the global right boundary R. R moves from zero to N and never decreases, so all fresh successful expansions total O(N); the outer loop adds O(N).
Mismatches cost at most one per position. This amortized argument, not the mere presence of a saved box, proves linear time and mirrors the right-boundary reasoning behind Manacher’s algorithm.
- Fresh matches advance R
- R never retreats
- Amortization proves O(N)
Pattern matching and borders
Build pattern + separator + text, choosing a separator absent from both inputs. Wherever Z[i] equals the pattern length, an occurrence begins at the corresponding text offset. The separator prevents a match from crossing the boundary.
A position i is a border start when i+Z[i]=N; the suffix beginning at i equals a prefix. Periodicity and compression tests follow from whether a candidate period covers the remainder through its Z value.
- Separator must be unique
- Full pattern-length Z values are matches
- Suffix-reaching boxes reveal borders
Implementation checks
Test empty strings according to the API, one character, all equal characters, no repeated prefix, overlapping occurrences, and a separator collision. Use i+Z[i]<N before indexing during expansion.
For Unicode, define whether indexes count bytes, code points, or grapheme clusters. Complexity is linear in the representation actually scanned; converting to code points may allocate additional storage.
- Bounds-check both compared positions
- Overlaps are natural
- Character representation affects indexing
Using Z values safely
When searching, convert an index in pattern+separator+text back by subtracting pattern length plus one. Report overlapping matches because each position is evaluated independently. For multiple separators or arbitrary binary data, avoid sentinel assumptions by using an integer alphabet with a reserved value.
Z and prefix-function arrays encode related border information but have different recurrences. Prefer Z when prefix matches at every suffix are directly useful; prefer KMP’s prefix function when failure transitions drive streaming matching. Converting conceptually does not justify mixing their index formulas.
For streaming input, the classic array assumes random access to the whole combined string. KMP may fit better when text arrives incrementally. If only one pattern search is required, both remain linear; constant factors, memory, and the desired auxiliary information guide the choice.
The linear bound comes from the fact that explicit character comparisons that extend a Z-box move R right, and R can advance at most n positions. Comparisons inside the current box are answered from a previously computed Z value and clipped to the remaining box length. This accounting is more informative than merely stating O(n): it explains why nested-looking while loops do not multiply into quadratic work. Test an all-equal string, a string with no repeated prefix character, periodic text, and a match that reaches the final character. These cases exercise maximum extension, zero values, copied values, and the exclusive right boundary.
- Translate concatenated indexes carefully
- Reserved separators handle arbitrary text
- Z and prefix functions are related but not interchangeable