Lab 10 — Z-Function & Manacher’s Algorithm

Goal

Implement two linear-time string scans. The Z-array: z[i] = length of the longest common prefix of s and s[i:] — “how far does the string match itself starting at i”. Manacher’s algorithm: the longest palindrome centered at every position, in O(n) exact. Apply Manacher to LC 5 (Longest Palindromic Substring) and Z to pattern matching and LC 214. Target: either scan from cold start in <12 minutes, both amortization arguments stated from memory.

Background Concepts

Z-box maintenance. The Z algorithm maintains the rightmost matched window [l, r): an interval where s[l..r-1] is already known to equal s[0..r-l-1]. When computing z[i] for i < r, position i mirrors position i − l in the prefix, so z[i] ≥ min(z[i−l], r−i) for free; only the part past r needs explicit comparison. Since r only ever advances, total explicit comparisons are O(n).

Relation to the KMP failure function (lab-05). fail[i] is “longest border looking backward at i”; z[i] is “prefix match looking forward from i”. They carry the same information and are interconvertible in O(n) in both directions. Z is often easier to reason about under pressure because z[i] is a direct statement about one suffix, not a chain of borders.

Manacher’s transform. Palindromes come in odd and even lengths — two center types. Transform s → t = '#' + '#'.join(s) + '#' (length 2n+1). Every palindrome in t is odd-length; rad[i] (radius in t) equals the length in s of the palindrome centered at transformed position i, and its start in s is (i − rad[i]) / 2. The mirror trick is the palindromic twin of the Z-box: inside the rightmost palindrome (c, r), position i inherits min(rad[2c−i], r−i) from its mirror 2c−i, then extends explicitly.

Interview Context

LC 5 is among the most frequently asked problems anywhere. The expected answer at most companies is expand-around-center O(n²); Manacher is the differentiator at L5+/quant/CP-flavored interviews — name it, state O(n), derive it if pushed. Z shows up wherever you need “prefix match at every position”: exact matching without hash-collision hand-waving, periodicity, string compression, LC 214. Interviewers who ask for Z usually want the amortization argument, not just the code.

Problem Statement (LC 5)

Given a string s, return the longest palindromic substring of s. Companion problem: given pattern and text, return all occurrence indices (generalized LC 28) — solve it with Z, no hashing.

Constraints

  • 1 ≤ s.length ≤ 1000 (LC 5); the O(n) solutions generalize to 10⁶.
  • s consists of digits and English letters (algorithm is alphabet-agnostic).
  • For search: pattern and text up to 10⁵ each; separator character must not occur in either.

Clarifying Questions

  1. If several longest palindromes exist, which one? (Any — LC 5 accepts all.)
  2. Is a single character a palindrome? (Yes — answer length ≥ 1 for nonempty s.)
  3. Substring or subsequence? (Substring, contiguous. Subsequence is LC 516 — a DP, different lab.)
  4. Case-sensitive? (Yes by default.)
  5. For search: overlapping occurrences reported? (Yes, all of them.)

Examples

longest_palindrome("babad") → "bab" (or "aba")
longest_palindrome("cbbd")  → "bb"        (even case — the transform earns its keep)
longest_palindrome("aaaa")  → "aaaa"
search("aa", "aaaa")        → [0, 1, 2]
z_function("aabxaayaab")    → [10, 1, 0, 0, 2, 1, 0, 3, 1, 0]
manacher("abba")            → [0, 1, 0, 1, 4, 1, 0, 1, 0]   (radii over "#a#b#b#a#")

Initial Brute Force

Palindromes: for each of the 2n−1 centers, expand outward while characters match; keep the best. Z: for each i, compare s[i:] against s character by character.

Brute Force Complexity

Both O(n²) worst case ("aaa…a" makes every expansion run to the boundary), O(1) extra space. At n = 1000 (LC 5) expand-around-center passes comfortably; at n = 10⁵–10⁶ it does not. Naive matching is O(n·m).

Optimization Path

Palindromes: expand-around-center O(n²) → binary search on answer length + rolling hash O(n log n), probabilistic (lab-06) → Manacher O(n), exact. Matching: naive O(n·m) → KMP (lab-05) or Z, both O(n+m) — same information, different indexing; Z’s concatenation trick (pattern + sep + text) turns matching into a single array scan with no matcher state machine to get wrong.

Final Expected Approach

def z_function(s):
    """z[i] = length of the longest common prefix of s and s[i:]. z[0] = n."""
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l, r = 0, 0                          # z-box: rightmost window with s[l:r] == s[0:r-l]
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])  # mirror value, clamped to the box
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                    # explicit extension past the box
        if i + z[i] > r:
            l, r = i, i + z[i]           # box only ever advances
    return z

def search(pattern, text):
    """All start indices of pattern in text. O(n + m)."""
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    z = z_function(pattern + '\x00' + text)
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] >= m]

def manacher(s):
    """Radii over t = '#' + '#'.join(s) + '#'. rad[i] equals the length (in s)
    of the longest palindrome centered at transformed position i."""
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    rad = [0] * n
    c, r = 0, 0                          # center / right edge of rightmost palindrome
    for i in range(n):
        if i < r:
            rad[i] = min(r - i, rad[2 * c - i])   # mirror trick
        while (i - rad[i] - 1 >= 0 and i + rad[i] + 1 < n
               and t[i - rad[i] - 1] == t[i + rad[i] + 1]):
            rad[i] += 1
        if i + rad[i] > r:
            c, r = i, i + rad[i]
    return rad

def longest_palindrome(s):
    """LC 5. O(n)."""
    if not s:
        return ""
    rad = manacher(s)
    i = max(range(len(rad)), key=lambda k: rad[k])
    start = (i - rad[i]) // 2            # transformed index → s index
    return s[start:start + rad[i]]

Data Structures Used

  • z / rad — int arrays over the (transformed) string.
  • Two maintained windows: z-box [l, r), rightmost palindrome (c, r). Nothing else — that is the point.

Correctness Argument

Z invariant: [l, r) is a window with s[l..r-1] == s[0..r-l-1] and maximal r seen so far. For i < r, the mirror gives z[i] ≥ min(z[i−l], r−i). If z[i−l] < r−i, the value is exact: a longer match at i would extend the mirror’s match inside the known-equal window — contradiction. If z[i−l] ≥ r−i, everything up to r matches but beyond r is unknown — extend explicitly. Either way z[i] is correct by induction.

Manacher: identical structure with palindromic mirroring — inside palindrome (c, r), the palindrome at i reflects the one at 2c−i; strictly-inside radii are exact, boundary-touching radii are extended explicitly. The '#' sentinels make every palindrome in t odd-length, so one center type covers both parities of s; the parity bookkeeping is free because a radius that “ends on a letter” is impossible in t.

Linearity (both): every successful explicit comparison advances r, and r never decreases → ≤ n successes total; each position adds at most one failed comparison → O(n).

Complexity

OperationTimeSpace
z_functionO(n)O(n)
searchO(n + m)O(n + m)
manacher / longest_palindromeO(n)O(n)

Implementation Requirements

  • State the z[0] convention explicitly (here: z[0] = n; some templates leave 0 — either is fine, mixing them is not).
  • search must use a separator that cannot occur in pattern or text ('\x00' for printable input).
  • manacher returns radii over the transformed string; the caller maps back with start = (i − rad[i]) // 2.
  • No recursion, single pass each, no per-iteration slicing.

Tests

  • Fixed: longest_palindrome on "babad", "cbbd", "a", "", "aaaa".
  • search("sad", "sadbutsad") == [0, 6]; overlapping: search("aa", "aaaa") == [0, 1, 2]; miss → [].
  • Hand-checked arrays: z_function("aabxaayaab") == [10,1,0,0,2,1,0,3,1,0], z_function("aaaaa") == [5,4,3,2,1], manacher("abba") == [0,1,0,1,4,1,0,1,0].
  • Stress: random strings over {a,b} and {a,b,c}, z vs char-by-char brute force, palindrome length vs O(n³) brute force, search vs slicing scan. (All of the above verified against brute force before this lab shipped.)

Follow-up Questions

  • Convert z[] to fail[] and back. → Both O(n). Z→fail: for each i with z[i] > 0 set fail[i+z[i]−1] = max(·, z[i]), then sweep right-to-left with fail[i] = max(fail[i], fail[i+1]−1). Fail→Z is symmetric. Knowing this means you never need both memorized under pressure.
  • Why is the while-loop amortized O(n)? → Each successful comparison pushes r forward and r is monotone non-decreasing, bounded by n; failures are ≤ 1 per position. Potential function: r itself.
  • Shortest Palindrome (LC 214). → Longest palindromic prefix of s. Via Z: build t = s + '#' + reverse(s); the prefix of length k is palindromic iff z[len(t)−k] == k; take the max k, prepend reverse(s[k:]). Via KMP: fail[-1] of the same concatenation. Same trick, two dialects.
  • Count distinct palindromic substrings. → Manacher counts palindromes with multiplicity (Σ⌈rad[i]/2⌉ over t solves LC 647). Distinct needs the palindromic tree (Eertree): O(n) nodes because a string has ≤ n+1 distinct palindromic substrings — one new node per appended character. Name-drop it; building one live is beyond interview scope.
  • String periodicity. → p is a period of s iff z[p] == n − p (the shifted suffix matches the prefix exactly). Smallest period: scan p = 1, 2, … Via the failure function the smallest period is n − fail[n−1] directly; s is an exact repetition iff that divides n (LC 459). Both characterizations are equivalent by border–period duality.
  • Z vs rolling hash for matching? → Z is exact and branch-predictable; hashing (lab-06) handles multiple patterns of the same length and 2-D cases but needs collision care. Prefer Z when one pattern, exact answer.

Product Extension

Genomics: restriction-enzyme sites and hairpin structures are (reverse-complement) palindromes — Manacher over a complement-mapped alphabet finds all maximal ones per chromosome in one linear pass, 10⁸+ characters. Log-pipeline dedup: Z-arrays of template + '\x00' + line classify millions of log lines against extracted templates without regex backtracking blowups. LZ77-style compressors compute Z-like longest-previous-match arrays as their core primitive.

Language/Runtime Follow-ups

  • Python: never slice inside the loop — s[z[i]] == s[i + z[i]] is O(1), s[i:].startswith(...) is O(n) per call and silently reintroduces O(n²). For 10⁶ chars, convert to bytes and index ints.
  • C++: the canonical CP versions; std::string + vector<int>. Some templates use sentinels '^'/'$' around t to delete the bounds checks — measurable at 10⁷.
  • Java: s.charAt per comparison is fine post-JIT; convert to char[] for hot loops.
  • Go: index []byte directly; avoid strings.Builder in the transform for large n — preallocate.
  • JS/TS: charCodeAt beats string equality on V8; typed Int32Array for z/rad.

Common Bugs

  1. Unclamped mirror copy: taking z[i] = z[i−l] without min(·, r−i) — beyond the box nothing is known; produces overcounts on inputs like "abababab".
  2. Updating the box unconditionally: writing l, r = i, i+z[i] even when i+z[i] ≤ r shrinks the box. Answers stay correct (it is still a valid match window) but linearity dies — the classic “my Z is O(n²) on aaaa…” bug.
  3. Skipping the transform: running odd-only expansion on raw s silently misses every even palindrome ("cbbd" → "c" instead of "bb").
  4. Wrong map-back: the start in s is (i − rad[i]) // 2, not (i − rad[i] − 1) // 2 — off-by-one here returns a string one char wide of the palindrome.
  5. Separator inside the alphabet: joining with '#' in search when the text may contain '#' lets matches straddle the boundary. Use '\x00' or a length guard.
  6. z[0] convention drift: template A sets z[0] = n, template B leaves 0; pasting the search loop from B under the array from A (or vice versa) is fine only because search skips index 0 — until someone iterates from 0.

Debugging Strategy

Hand-compute z for a 10-char string and diff ("aabxaayaab" → [10,1,0,0,2,1,0,3,1,0]). Instrument the loop to print (i, l, r, z[i]): r must be non-decreasing across the entire run — if it ever drops, bug 2 is present. For Manacher, print t with rad aligned beneath it and eyeball the peak: for "abba", the 4 must sit on the middle '#' at index 4. If the peak sits on a letter for an even palindrome, the transform is wrong.

Mastery Criteria

  • Wrote z_function from cold start in <8 minutes, correct on "aaaaa" and "abababab" first run.
  • Wrote manacher + longest_palindrome in <12 minutes, even palindromes included.
  • Solved LC 5, LC 214, LC 647 from cold start.
  • Computed z for an unfamiliar 10-char string by hand in <2 minutes.
  • Stated the r-monotonicity amortization argument without prompting.
  • Stated the period test both ways (z-based scan; n − fail[n−1] via lab-05) and when each applies.