Z-Algorithm Visualization | Z-Box and Linear Search

The idea: how far does each suffix match the start?

For a string S of length n, the Z value Z[i] is the length of the longest substring starting at i that is also a prefix of S. For S = aabxaabxcaabxaabxay, Z[4] = 4 because aabx starts at 4 and also at 0, and the next characters (c and a) differ. Z[0] would be the whole string and is left undefined. The list of all Z values is the Z array.

The string aabxaabxcaabxaabxay with its Z array. The Z-box [9, 16] is marked in orange over aabxaabx at positions 9 to 16, and its copy [0, 7] in blue at the start. Position i = 13 inside the box has the twin k = i − l = 4 in the copy, whose Z[4] = 4 is already known. — Inside the Z-box [l, r] the string repeats its own start, so position i can look up its twin k = i − l instead of comparing.

Computing each Z value by sliding the prefix under position i and comparing until a mismatch costs O(n²) in the worst case: 105 compares for fifteen as. The Z-algorithm (Gusfield's presentation of an older idea of Main and Lorentz) gets the whole array with fewer than 2n compares by remembering what it has already matched.

The Z-box and its three cases

The algorithm walks i = 1, 2, …, n − 1 and keeps the Z-box [l, r]: of all matches found so far, the one that reaches furthest right. It says S[l..r] = S[0..r − l], so every position inside the box has a twin k = i − l near the start whose Z value is already known.

Three cases from the string aabxaabxcaabxaabxay. Case 1, i = 9 is past r = 7: compare from scratch, 9 compares, Z = 8. Case 2a, i = 10 inside [9, 16]: twin Z[1] = 1 is less than r − i + 1 = 7, so Z[10] = 1 with no compares. Case 2b, i = 13 inside [9, 16]: twin Z[4] = 4 equals r − i + 1 = 4, so the first 4 characters are known and only S[17] onward is compared: Z[13] = 5. — Outside the box: compare. Inside, the twin's match either ends inside the box (copy it) or reaches its edge (compare only past r).

case	test	what the algorithm does
1: outside	i > r	Compare S[0], S[1], … with S[i], S[i+1], … until a mismatch.
2a: copy	Z[k] < r − i + 1	Z[i] = Z[k] with no compare: the twin's match ends inside the copy, so the match at i ends at the same place.
2b: extend	Z[k] ≥ r − i + 1	The first r − i + 1 characters are known to match. Compare from S[r + 1] on.

Whenever a match from i ends past r, the box moves to [i, i + Z[i] − 1]. (Demos: inside the Z-box, copy Z[k], where i = 10 copies Z[1] = 1, and Z[k] reaches the box edge, where i = 13 compares only S[17] and S[18].)

l = r = 0
for i = 1 .. n−1:
    if i > r:                    k = 0                      # case 1
    else if Z[i−l] < r−i+1:      Z[i] = Z[i−l]; continue    # case 2a
    else:                        k = r−i+1                  # case 2b
    while i+k < n and S[k] == S[i+k]: k = k+1
    Z[i] = k
    if i+k−1 > r: l, r = i, i+k−1

Why it is linear

Every compare that finds two equal characters is at a position past the old r, and the box then moves so that r covers it. Since r only moves right and stops at n − 1, there are fewer than n equal compares in total. Each position ends with at most one unequal compare, so fewer than n of those too. The whole Z array costs under 2n compares and O(n) time. On the page: 23 compares for the 19-character string (restarting at every i: 40), and 14 for fifteen as (restarting: 105). (Demos: whole Z array and aaaaaaaaaaaaaaa.)

Searching with P$T

To find a pattern P (length m) in a text T, build S = P + $ + T, where $ occurs in neither string. No match can run past the $, so no Z value exceeds m, and Z[i] = m exactly where the whole pattern starts: at position i − m − 1 of T. Overlapping matches are found too. The cost is O(n + m).

In abab$abacababab the two Z values equal to m = 4 are the two (overlapping) matches of abab in the text.

(Demo: search abab in abacababab: matches at text positions 4 and 6.)

Z-algorithm vs KMP

KMP solves the same problem in the same time with its failure table (the prefix function). The two tables carry the same information in different shapes, and each can be computed from the other in linear time.

	Z-algorithm	KMP
table	Z[i]: longest prefix starting at i	π[i]: longest proper prefix of S[0..i] that is also its suffix
search	Z array of P$T, look for Z = m	table of P, then one pass over T
time	O(n + m), under 2(n + m) compares	O(n + m), under 2n + 2m compares
memory	the whole P$T and n + m + 1 Z values	m table entries; T can be a stream
on this page: abab in abacababab	18 compares	3 (table) + 12 (scan) = 15 compares

KMP is the better fit when the text arrives as a stream or is too large to copy. The Z-algorithm is easier to state and to get right, which is why it is popular in programming contests, and the Z array answers other questions directly: the periods of a string, the number of distinct substrings, and string compression. See String Search Race for KMP, Boyer-Moore and Rabin-Karp on the same text.

What the page leaves out

The page uses short strings over a small alphabet and counts character compares only, not the index arithmetic around them. It skips the conversions between the Z array and KMP's prefix function, the use of the Z-algorithm as the preprocessing step of Boyer-Moore's good-suffix rule, searching without the $ by computing Z values of P and matching T against them, and the Main-Lorentz algorithm for finding repetitions, which is where the idea comes from.