Z-Algorithm Intuition

The Idea

z[i] is how many characters from position i match the start of the string. Comparing every position from scratch is quadratic, so keep the rightmost match found so far — the z-box. A position inside that box was already compared once, at its mirror near the front, so its answer starts from the mirror's value and only the part beyond the box is compared again. The box only ever slides right.

Real-World Example

A file-diff tool asking where a file starts repeating its own header. It never re-reads a stretch it has already proved identical; it picks up at the furthest point it has confirmed and compares from there.

The Code

def z_array(s):
    z = [0] * len(s)
    lo = hi = 0                             # the live z-box
    for i in range(1, len(s)):
        if i < hi:
            z[i] = min(hi - i, z[i - lo])   # reuse the box's mirror
        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
            z[i] += 1                       # extend past the box
        if i + z[i] > hi:
            lo, hi = i, i + z[i]            # a longer box: keep it
    return z

print(z_array("aabxaab"))   # [0, 1, 0, 0, 3, 1, 0]

for i in range(1, len(s)):
  if i < hi:
      z[i] = min(hi - i, ___)
  while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
      z[i] += 1