DSA The Z Algorithm
The Z algorithm computes, for every position in a string, how many opening letters repeat starting there. A Z-box is the stretch already known to match the opening of the string.
Reading a Z array
In aaaa, every position repeats the opening for the rest of the string. The longer string mixes long matches, short matches, and zeros.
def z_array(text):
n = len(text)
z = [0] * n
left = 0
right = 0
comparisons = 0
for i in range(1, n):
if i <= right:
z[i] = min(right - i + 1, z[i - left])
while i + z[i] < n:
comparisons += 1
if text[z[i]] != text[i + z[i]]:
break
z[i] += 1
if i + z[i] - 1 > right:
left = i
right = i + z[i] - 1
return z, comparisons
print("String: aaaa")
print("Z array:", z_array("aaaa")[0])
print("String: aabcaabxaaaz")
print("Z array:", z_array("aabcaabxaaaz")[0])Inside a Z-box
The match at index 4 opens a box that covers indices 4 to 6. Index 5 lies inside it, so its value starts as a copy of the Z value at index 1.
def z_array(text):
n = len(text)
z = [0] * n
left = 0
right = 0
comparisons = 0
for i in range(1, n):
if i <= right:
z[i] = min(right - i + 1, z[i - left])
while i + z[i] < n:
comparisons += 1
if text[z[i]] != text[i + z[i]]:
break
z[i] += 1
if i + z[i] - 1 > right:
left = i
right = i + z[i] - 1
return z, comparisons
text = "aabcaabxaaaz"
z, comparisons = z_array(text)
print("Z at index 4:", z[4])
print("Box from index 4 covers:", 4, "to", 4 + z[4] - 1)
print("Inside the box, index 5 copies Z at:", 5 - 4)
print("Comparisons used:", comparisons)Matching by concatenation
The pattern, a separator, and the text form one string. Any Z value reaching the pattern length marks a full match.
def z_array(text):
n = len(text)
z = [0] * n
left = 0
right = 0
comparisons = 0
for i in range(1, n):
if i <= right:
z[i] = min(right - i + 1, z[i - left])
while i + z[i] < n:
comparisons += 1
if text[z[i]] != text[i + z[i]]:
break
z[i] += 1
if i + z[i] - 1 > right:
left = i
right = i + z[i] - 1
return z, comparisons
def find_all(text, pattern):
joined = pattern + "$" + text
z, _ = z_array(joined)
found = []
for i in range(len(pattern) + 1, len(joined)):
if z[i] >= len(pattern):
found.append(i - len(pattern) - 1)
return found
print("Matches of abc in abcyabc:", find_all("abcyabc", "abc"))Example
def z_array(text):
n = len(text)
z = [0] * n
left = 0
right = 0
comparisons = 0
for i in range(1, n):
if i <= right:
z[i] = min(right - i + 1, z[i - left])
while i + z[i] < n:
comparisons += 1
if text[z[i]] != text[i + z[i]]:
break
z[i] += 1
if i + z[i] - 1 > right:
left = i
right = i + z[i] - 1
return z, comparisons
def z_naive(text):
n = len(text)
z = [0] * n
comparisons = 0
for i in range(1, n):
k = 0
while i + k < n:
comparisons += 1
if text[k] != text[i + k]:
break
k += 1
z[i] = k
return z, comparisons
for text in ["abababab", "aaaaaaab"]:
z, smart = z_array(text)
plain_z, plain = z_naive(text)
print("String:", text)
print("Z array:", z)
print("Naive agrees:", plain_z == z)
print("Z comparisons:", smart)
print("Naive comparisons:", plain)Key points
- The Z value at index i counts the letters matching the string opening, starting at i
- The first entry is left as 0 by convention, since the whole string always matches itself
- A Z-box is stored as its left and right ends, and positions inside it copy earlier Z values
- Only a position past the box's right end pays for fresh letter comparisons
- Joining a pattern, a separator, and a text turns the Z array into a pattern search
In this example, two strings get their Z arrays from the box-based algorithm. A naive version recomputes every position from scratch and agrees on both arrays. The comparison counts show the saving, and the second string widens the gap. Its long run of one letter is exactly where the naive version repeats the most work.
Note
The separator must be a character that appears in neither the pattern nor the text
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
In the Z array of a string, the value at index 6 is 4. What does that value state?