Z-algorithm

The Z-algorithm answers a different question from KMP’s table, in the same O(n) time: at each place of a string, how long a start of the whole string begins there? It is often easier to remember and to get right, and it reuses its own earlier answers in a way that is easy to see.

The Z-array

For a string s with n letters, Z[i] is the length of the longest piece starting at place i that is also a start of s. In other words, the longest common prefix of s and s[i:]. A common prefix of two strings is a start they share.

s   a  a  b  a  a  b  a  a
Z   –  1  0  5  1  0  2  1
# Z[3] = 5: s[3:] = "aabaa" begins with "aabaa", the first 5 letters of s
# Z[2] = 0: s[2] = "b" but s[0] = "a"

Z[0] would be n, the whole string; it is usually left out or set to 0. Working out each Z[i] on its own, letter by letter, costs O(n²) on a string like "aaaa…", where every answer is long.

The box

The method keeps the box [l, r): of all the matches found so far (pieces s[i..i + Z[i])), the one that reaches furthest right. The box is a copy of the start of s: s[l..r) = s[0..r − l).

Now take a place i inside the box, l < i < r. Because the box is a copy, the letters from i to r are the same as the letters from i − l to r − l, and Z[i − l] is already known.

• If Z[i − l] < r − i: the match at i − l stops inside the copy, at a letter that differs from the start of s. The same letter appears at the same spot after i, so the match at i stops there too. No comparisons are needed.
• Otherwise: the first r − i letters are known to match, but nothing is known past r. Compare from there on, letter by letter.

For a place outside the box, compare from the start. Whenever a match reaches past r, it becomes the new box.

# one place i, with the box [l, r) from the places before it
if i < r:
    z[i] = min(r - i, z[i - l])     # the box rule
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
    z[i] += 1                       # compare on, letter by letter
if i + z[i] > r:                    # this match reaches further right
    l, r = i, i + z[i]

The code does not check the case Z[i − l] < r − i on its own: there, the first comparison of the while loop fails at once. Step through the figure. Places 4 and 5 copy their answers from places 1 and 2 with no comparisons; places 6 and 7 start from what the box gives and find nothing left to compare.

Why it is O(n)

Count the comparisons in the while loop. Each one either fails, which happens at most once per place (n in all), or succeeds. A comparison that succeeds looks at the letter s[i + Z[i]], which is at or past r: everything before r is covered by the box rule. So each success pushes the right end of the match past the old r, and then r moves there. r never moves left and never goes past n, so there are at most n successes. In all, at most 2n comparisons: O(n) time.

Matching with a separator

To find a pattern P (length m) in a text T, build the Z-array of P + "$" + T, where $ is a letter that occurs in neither. No match can run across the $, so no value is more than m. P occurs at place i of T exactly when the value at place m + 1 + i of the joined string is m.

The same values tell you more than KMP’s places: z[m + 1 + i] is how much of the start of P begins at place i of T, even where P does not fully occur. STRG-P3 asks for those values, so it needs the whole method: the loop over every place i with the step above, starting from l = r = 0.

Z or π?

• Both cost O(n + m) and use the same amortised count: a pointer that only moves one way.
• Each can be built from the other in O(n). For example, a match at place i of length Z[i] means that the start of s of that length ends at place i + Z[i] − 1, so π[i + Z[i] − 1] ≥ Z[i].
• π suits text that arrives one letter at a time (a stream); Z needs the whole string first.
• Z is handy for questions about starts: the shortest period is the smallest i with i + Z[i] = n; and the number of different pieces of a string can be counted by adding letters one at a time and taking the Z-array of the reversed string each time (O(n²) in all, fine for a few thousand letters).

Now try STRG-P3, How much of the pattern fits.