Z-algorithm — Z-array construction, O(n+m)

WHAT is the Z-array?

Concretely $Z[i] = \max\{ k : s[0..k-1] = s[i..i+k-1] \}$ .

WHY does the naive version cost $O(n^2)$ — and how do we fix it?

Naive: for each $i$ , compare $s[i+k]$ vs $s[k]$ until mismatch. Worst case aaaa...a → each $i$ scans to the end → $\sum i = O(n^2)$ .

HOW to build it — derivation from scratch

We maintain a window $[l, r]$ = rightmost segment matching the prefix found so far (start $l=r=0$ ).

For each $i$ from $1$ to $n-1$ , two cases:

Case A — $i > r$ (we're outside any known box). We have no information. Compare from scratch: $Z[i] = \max\{k : s[k] = s[i+k]\}$ starting at $k=0$ . If $Z[i]>0$ , set the new box $l=i,\ r=i+Z[i]-1$ .

Case B — $i \le r$ (we're inside the box). Let $i' = i - l$ be the mirror position in the prefix. We know $Z[i']$ . Two sub-cases:

B1: $Z[i'] < r-i+1$ . The mirror's match fits entirely inside the box. Since inside the box $s$ equals the prefix exactly, the match at $i$ is identical: $Z[i] = Z[i']\quad(\text{no comparisons, no box update})$ Why no comparison? Because the mismatch that ended the mirror's match is still inside the box, so it's guaranteed to repeat at $i$ .
B2: $Z[i'] \ge r-i+1$ . The mirror's match reaches the box boundary; beyond $r$ we have no guarantee, so we must compare manually starting from $k = r-i+1$ : $Z[i] = (r-i+1) + (\text{extra matches found by comparing } s[k] \text{ vs } s[i+k])$ Then update box to $l=i,\ r=i+Z[i]-1$ .

Formula The whole algorithm

l = r = 0
Z[0] = 0
for i in 1 .. n-1:
    if i <= r:                    # Case B: inside box
        Z[i] = min(r - i + 1, Z[i - l])
    while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:   # extend (B2 / Case A)
        Z[i] += 1
    if i + Z[i] - 1 > r:          # new rightmost box
        l = i
        r = i + Z[i] - 1

The single while loop elegantly handles Case A (initial $Z[i]=0$ ) and B2. The min handles B1 by capping at the box edge so the while does zero extra work when the mirror fit inside.

Figure — Z-algorithm — Z-array construction, O(n+m)

WHY is the total cost $O(n+m)$ ?

Pattern matching application

To find pattern $p$ (length $m$ ) in text $t$ (length $n$ ): build string $S = p + \texttt{\#} + t \qquad (\texttt{\#}\notin p,t)$ Compute $Z$ over $S$ (length $m+1+n$ ). Wherever $Z[i] = m$ , the pattern occurs in $t$ at position $i-(m+1)$ . Total cost $O(n+m)$ .

Worked example Full trace:

$s=\texttt{aabaab}$ Indices 0..5.

$i=1$ : $i>r(=0)$ → compare: s[0]=a,s[1]=a✓; s[1]=a,s[2]=b✗ → $Z[1]=1$ . New box $l=1,r=1$ . Why box? $i+Z-1=1>0$ .
$i=2$ : $i=2>r=1$ → compare: s[0]=a vs s[2]=b✗ → $Z[2]=0$ . No box.
$i=3$ : $i=3>r=1$ → compare aab vs aab (s[0..2] vs s[3..5]) → matches 3, then end → $Z[3]=3$ . Box $l=3,r=5$ .
$i=4$ : $i=4\le r=5$ , mirror $i'=1$ , $Z[1]=1$ , $r-i+1=2$ . $\min(2,1)=1$ . while: s[1]=a vs s[5]=b✗ → stays $Z[4]=1$ . (B1: cheap copy, no extension.)
$i=5$ : $i=5\le r=5$ , mirror $i'=2$ , $Z[2]=0$ , $\min(1,0)=0$ . while: s[0]=a vs s[5]=b✗ → $Z[5]=0$ .

Result: $Z=[-,1,0,3,1,0]$ . ✔

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine the first few letters of a word are your "secret code". You walk along the rest of the word asking at each spot: "Starting here, how many letters match the start of the word?" The slow way is to re-check from zero each time. The clever trick: if you already matched a long chunk earlier, that chunk is a photocopy of the beginning — so a spot inside it must behave the same as the matching spot near the start. You just look up the answer you already wrote down, instead of re-counting. You only do new counting when you walk past the edge of the photocopied chunk — and since that edge only ever moves forward, you never do too much work.

Flashcards

What does Z[i] represent?

The length of the longest substring starting at index i that is also a prefix of s.

Why is naive Z computation O(n²)?

For strings like "aaa...a" each starting index re-scans to the end, summing to O(n²) comparisons.

What is the Z-box [l,r]?

The rightmost (largest r) interval already known to match the prefix: s[l..r] = s[0..r-l].

In Case B (i ≤ r), what is the mirror index?

i' = i - l; the corresponding position inside the prefix.

Why can we copy Z[i-l] inside the box without comparing?

Inside [l,r] the string equals the prefix, so s[i]=s[i-l]; the mirror's match (and its terminating mismatch) repeat exactly — if it stays within the box. :::

What does min(r-i+1, Z[i-l]) protect against?

Claiming matches beyond r that were never verified; it caps trust at the box boundary.

When do you update the box?

Only when i + Z[i] - 1 > r, i.e. the new match extends further right than the current box.

Why is the total cost O(n)?

Each inner while-iteration increases r by 1; r only grows and is ≤ n-1, so total extensions ≤ n.

How to do pattern matching with Z?

Build S = pattern + '#' + text, compute Z; positions where Z[i]=m (pattern length) are matches.

Why must the separator '#' be absent from both strings?

Otherwise a Z-match could span the boundary and report a false occurrence.

Connections

String Hashing — alternative O(n) substring-match tool; Z avoids hash collisions.
KMP failure function — also computes prefix-match info; Z and the prefix-function are inter-convertible.
Suffix Array / Suffix Automaton — heavier structures for repeated queries.
Amortized Analysis — the " $r$ only increases" argument is a potential-function classic.
Manacher's Algorithm — same "reuse the symmetric/mirror box" trick for palindromes.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Z-algorithm ka kaam simple hai: har index $i$ ke liye batao ki wahan se shuru karke kitne characters string ke prefix se match karte hain. Yeh value Z[i] kehlati hai. Agar tum naive tarike se har position pe zero se compare karoge to worst case (jaise "aaaa...") mein $O(n^2)$ ho jata hai — bahut slow.

Trick yeh hai: jab tumne pehle se koi lamba match dhoond liya, to ek "Z-box" $[l,r]$ banta hai jo prove karta hai ki $s[l..r]$ bilkul prefix jaisa hai — yaani uska photocopy. Ab agar tumhe kisi $i$ ka Z chahiye jo is box ke andar hai, to box ke andar ka character $s[i]$ exactly $s[i-l]$ ke barabar hai. Iska matlab Z[i-l] (mirror position) ka answer tum free mein copy kar sakte ho — koi comparison nahi! Sirf jab tum box ke right edge $r$ se aage nikalte ho, tab actual comparison karte ho.

Aur yahi linear time ka raaz hai: har baar jab tum aage compare karte ho aur match milta hai, $r$ ek aage badh jata hai. $r$ kabhi peeche nahi jata aur $n$ se zyada nahi ho sakta — isliye total extra comparisons sirf $n$ tak. Bas yaad rakho: min(r-i+1, Z[i-l]) lagana zaroori hai, warna tum box ke bahar wale unverified matches claim kar baithoge.

Pattern matching ke liye to bilkul mast use hota hai: $S = pattern + \texttt{\#} + text$ banao, Z nikaalo, aur jahan $Z[i] = m$ (pattern length) wahan match mil gaya — sab $O(n+m)$ mein. Competitive programming mein yeh ek must-know weapon hai.

Z-algorithm — Z-array construction, O(n+m)

WHAT is the Z-array?

WHY does the naive version cost $O(n^2)$ — and how do we fix it?

HOW to build it — derivation from scratch

WHY is the total cost $O(n+m)$ ?

Pattern matching application

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections

i	0	1	2	3	4	5	6	7	8	9
s	a	a	b	x	a	a	y	a	a	b
Z	–	1	0	0	2	1	0	3	1	0