1. The $[L, R]$ Z-Box Invariant & Mirror Index $k = i - L$
At iteration $i \in [1, N-1]$, let $[L, R]$ be the rightmost interval discovered so far ($L < i$) such that $S[L..R] = S[0..R-L]$. There are two possibilities for $i$:
- Case 1 ($i > R$): Index $i$ lies strictly outside the current Z-Box. We have no prior information about $S[i]$, so we compare $S[0..]$ with $S[i..]$ character by character to find $Z[i]$, and if $Z[i] > 0$, set $L = i, R = i + Z[i] - 1$.
- Case 2 ($i \le R$): Index $i$ lies inside $[L, R]$. By the Z-Box invariant, $S[i..R] = S[i-L .. R-L]$. Therefore, the first $R - i + 1$ characters starting at $i$ are identical to the characters starting at $k = i - L$:
- Subcase 2a ($Z[i - L] < R - i + 1$): The prefix match at $i - L$ terminated strictly before reaching $R - L$. Thus the match at $i$ MUST also terminate at the exact same offset: $Z[i] = Z[i - L]$ in $O(1)$ time with zero character comparisons!
- Subcase 2b ($Z[i - L] \ge R - i + 1$): We know at least the first $R - i + 1$ characters match ($Z[i] \ge R - i + 1$), and the match might extend past $R$. We initialize $Z[i] = R - i + 1$, extend character-by-character starting at $R + 1$, and update $[L, R] = [i, i + Z[i] - 1]$.
One-Line Z-Initialization & Monotonicity of $R$: Both Case 1 and Case 2 unify into a single initialization:
$$Z[i] = (i \le R) \;\text{?}\; \min(R - i + 1, Z[i - L]) : 0$$
Followed by
while (i + Z[i] < N && S[Z[i]] === S[i + Z[i]]) Z[i]++;. Notice that whenever the while loop executes even a single successful comparison, $i + Z[i] - 1$ strictly exceeds $R$, which immediately increments $R$! Since $R < N$ never decreases, the while loop makes at most $N$ successful character comparisons across the entire algorithm ($Theta(N)$ time).
flowchart TD
Loop["For i = 1 to N - 1"] --> Init["If i <= R: z[i] = min(R - i + 1, z[i - L])
Else: z[i] = 0"]
Init --> Ext["While i + z[i] < N and S[z[i]] == S[i + z[i]]:
z[i]++"]
Ext --> Upd{"i + z[i] - 1 > R?"}
Upd -- Yes --> SetLR["L = i
R = i + z[i] - 1"]
Upd -- No --> Next["Next i"]
SetLR --> Next
Hardware & Cache Reality — Duality Between $Z[]$ and $\pi[]$: The Z-array and KMP prefix function carry equivalent structural information and can be converted into one another in $\Theta(N)$ time! Specifically, given $Z[1..N-1]$, every index $i$ sets $\pi[i + Z[i] - 1] = \max(\pi[i + Z[i] - 1], Z[i])$, followed by a backward pass $\pi[i] = \max(\pi[i], \pi[i+1] - 1)$. In practice, the Z-algorithm is often faster than KMP when you need the LCP of every suffix $S[i..]$ against $S[0..]$ directly.
KMP Prefix Function π[i], Z-Box [L, R] & Linear Automaton Stepper
Guaranteed O(N + M) Linear Time
Trace how KMP never backs up the text pointer (using π[j−1] fallback borders with potential Φ = j ≤ i) and how the Z-Algorithm reuses previously matched [L, R] Z-boxes.
Step 1 / 9
Timeline
Invariant & State
Amortized Potential Φ = j = 0 ≥ 0 | j increments at most once per step i, so fallback j = π[j−1] runs ≤ N times total!
🌳 Live 2D Hierarchical Tree Topology — KMP Prefix Function π[i], Z-Box [L, R] & Linear Automaton Stepper
Visited/Active
Pivot/Root
Resolved
[0]Aπ=0
[1]B
[2]A
[3]B
[4]C
[5]A
[6]B
[7]A
[8]B
Index i / Char
i = 0 ('A')
Border Length π[i]
0
Matched Prefix
ε (empty)
Total Work
O(M) Linear
[Step 1] i=0 ("A"): base case π[0] = 0.
2. Production Implementation: Z-Algorithm & $O(N + M)$ Pattern Matching
/**
* Computes the Z-Array z[0..N-1] in exact Theta(N) time and space.
* z[i] = length of the longest common prefix between S and the suffix S[i..N-1].
*/
function computeZArray(str) {
const n = str.length;
const z = new Int32Array(n);
if (n === 0) return z;
z[0] = n;
let l = 0, r = 0;
for (let i = 1; i < n; i++) {
if (i <= r) {
const k = i - l;
const rem = r - i + 1;
z[i] = z[k] < rem ? z[k] : rem;
}
while (i + z[i] < n && str.charCodeAt(z[i]) === str.charCodeAt(i + z[i])) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
/**
* Finds all occurrences of pattern in text using the Z-Algorithm without
* allocating a concatenated string P + '$' + T! Uses only O(M) extra memory.
*/
function zPatternSearch(text, pattern) {
const n = text.length, m = pattern.length;
if (m === 0) return [];
const zPat = computeZArray(pattern);
const matches = [];
let l = -1, r = -1;
for (let i = 0; i < n; i++) {
let matchLen = 0;
if (i <= r) {
const k = i - l;
const rem = r - i + 1;
matchLen = zPat[k] < rem ? zPat[k] : rem;
}
while (
matchLen < m &&
i + matchLen < n &&
pattern.charCodeAt(matchLen) === text.charCodeAt(i + matchLen)
) {
matchLen++;
}
if (i + matchLen - 1 > r) {
l = i;
r = i + matchLen - 1;
}
if (matchLen === m) {
matches.push(i);
}
}
return matches;
}3. Complexity Matrix
| Task | Concatenated Z-Array ($P + \text{'\$'} + T$) | Streaming Z-Search ($z_{\text{pat}}$ only) | Binary Search + Rolling Hash |
|---|---|---|---|
| Compute $\text{LCP}(S[0..], S[i..])$ for all $i$ | $\Theta(N)$ time, $\Theta(N)$ space | — | $\Theta(N \log N)$ time, $\Theta(N)$ space |
| Exact Pattern Matching ($|T|=N, |P|=M$) | $\Theta(N + M)$ time, $\Theta(N + M)$ space | $\Theta(N + M)$ time, $\Theta(M)$ space | $\Theta(N + M)$ time (probabilistic) |
Common Pitfall — Forgetting to Clamp
Z[i - L] by R - i + 1 or Omitting a Unique Separator:
- When $i \le R$, we only know that $S[i..R]$ matches $S[i-L .. R-L]$—we know nothing about characters beyond index $R$! If $Z[i - L] > R - i + 1$, copying
z[i] = z[i - L]without clamping byMath.min(R - i + 1, z[i - L])assumes characters past $R$ matched without ever inspecting them! - When using the $P + \text{sep} + T$ trick, if
sepcan appear inside $P$ or $T$ (and you don't cap matches at $M$), $Z[i]$ can exceed $M$. Using the streamingzPatternSearch(text, pattern)above avoids choosing a separator character altogether and uses only $O(M)$ memory.