Z-Algorithm · Podium

Z[0] = 0 (or n, by taste). For i > 0, Z[i] is the longest prefix of s that starts at i. If you already computed a window [l, r] that covers i (a previous match of s[0..r-l] onto s[l..r]), then Z[i] is at least min(Z[i-l], r-i+1) and you only extend when that bound is tight.

String matching: Z of pattern + '#' + text. Hits where Z[i] === pattern.length.

π and Z determine each other; learn both. Z is often cleaner for 'LCP with the whole string.' π is cleaner for borders and automata.

Classic Z-arrayjs

function zArray(s) {
  const n = s.length;
  const z = Array(n).fill(0);
  let l = 0;
  let r = 0;
  for (let i = 1; i < n; i++) {
    if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

TRACE

Z of 'aabcaabxaa'. Focus on how [l,r] saves comparisons.

i=1 'a'

s[0]='a' matches. Z[1]=1. Window [1,1].

Z[1]=1

1 / 4

CHECK

The inner while looks O(n²). Why is Z linear?

CHECK

You need the LCP of two arbitrary suffixes i and j. Is one Z-array enough?

Checks 0/2

Next lesson