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

Before you can read the parent note, you must own every piece of notation it throws at you. Below, each symbol is built from nothing: plain words → the picture → why the topic needs it. Read top to bottom; each one leans on the previous.

1. A string, and what "index" means

Picture a row of boxes, each holding one letter, with a small number written under each box.

• $s[0]$ means "the character in slot 0" — the very first one.
• $s[i]$ means "the character in slot $i$".

2. Substring — a contiguous slice

The key word is contiguous — no gaps, no skipping. aab is a substring of aabxaa; abx (in that order, adjacent) is too; but axa is not because the letters aren't next to each other.

3. Prefix — the string's signature

Picture sliding a cut-line from left to right: everything to the left of the cut is a prefix. The prefix of length $k$ is $s[\mathrm{0..}k-1]$ (it has $k$ characters, occupying slots $0$ through $k-1$).

4. Equality of two substrings

If even one pair of letters differs, the whole equality is false. This is exactly a match. When we say "$s[i..i+k-1]$ matches the prefix $s[\mathrm{0..}k-1]$", we mean all $k$ pairs agree.

5. The Z-value $Z[i]$

Now we can build the star symbol of the topic.

Let's earn every piece of that formula, left to right:

• $k$ is a candidate match-length we're testing.
• $s[\mathrm{0..}k-1]$ is the prefix of length $k$ (from section 3).
• $s[i..i+k-1]$ is the slice of length $k$ that starts at $i$ (from section 2 — note it has $k$ boxes because $(i+k-1)-i+1=k$).
• The "$=$" asks: are those two slices identical (section 4)?
• $\max \{\dots \}$ says: among all $k$ that make them equal, take the biggest. That's the longest photocopy of the beginning that starts here.

6. The window $[l,r]$ — the "Z-box"

The width of that box is $r-l+1$ (section 2's counting rule again).

7. The mirror index $i^{\prime }=i-l$

Picture the box laid on top of the prefix — they're identical copies. Slot $i$ sits some distance $i-l$ from the box's left edge $l$; slot $i^{\prime }$ sits that same distance from the prefix's left edge (slot $0$). So $i^{\prime }$ is $i$'s reflection in the "photocopy."

Because the box equals the prefix, $s[i]=s[i^{\prime }]$ — a fact, not a guess. That fact is what lets us copy the already-computed $Z[i^{\prime }]$ for free.

The prerequisite map

Each foundation feeds the next; the two arrows into "Z value" (prefix + equality) and the two into "min cap" (mirror + counting) are the load-bearing joins.

Where this sits in the bigger picture

The Z-array is one of several ways to encode "how does a string repeat inside itself." Its close cousin is the KMP failure function (which measures longest border instead of longest prefix-match). For a full trace with the same running example in Hindi/English mix, see 3.8.04 Z-algorithm — Z-array construction, O(n+m) (Hinglish). The linear-time speed claim rests on Amortized Analysis (the "$r$ only moves right" argument). Other tools for the same family of problems: String Hashing, Suffix Array, Suffix Automaton, and for palindromes the mirror-trick reappears in Manacher's Algorithm. All of these build on the same foundations above, so mastering them here pays off everywhere.

Once you're comfortable with these symbols, head to the parent: 3.8.4 Z-algorithm — Z-array construction, O(n+m).

Equipment checklist

Cover the right side and answer aloud; reveal to check.