Z algorithm: match every suffix start
Picture
For each position i, how many characters from s[i:] match the beginning of s?
Predict
What does Z[i] measure?
Walk through the small example
Prefix match length starting at i. A rightmost verified match interval can seed answers for positions inside it.
Mental model and complete Python solution
Keep the rightmost window known to match the prefix. A point inside sees a mirrored prefix answer, clipped by the window; only the unknown edge needs new comparisons.
What the function promises: Return Z values with Z[0]=len(text). Empty input returns an empty list.
def z_values(text):
n = len(text)
if n == 0: return []
z = [0] * n
z[0] = n
left = right = 0
for i in range(1, n):
if i <= right:
z[i] = min(right-i+1, z[i-left])
while i+z[i] < n and text[z[i]] == text[i+z[i]]:
z[i] += 1
if i+z[i]-1 > right:
left, right = i, i+z[i]-1
return z
assert z_values("aabcaabxaaaz") == [12,1,0,0,3,1,0,0,2,2,1,0]
assert z_values("") == []Work and storage: O(n) time and O(n) space.
When to recognize it: A rightmost verified match interval can seed answers for positions inside it.
Check before applying it: Concatenating pattern and text needs a separator absent from both, or a structured representation.
Change one rule
Need pattern occurrences in a text.
See what changes
Compute Z on pattern + a safe separator + text and select positions whose Z value reaches the pattern length.
Connect
KMP: reuse a matched prefix: Both preprocess prefix self-similarity with different tables.
Longest Palindromic Substring: Manacher reuses a rightmost box around palindrome centers.