05 — String Algorithms

Phase 5 | Weeks 33–34 | Mar 16 – Mar 29, 2027

Naive string matching is O(n·m): for each position in the text, try matching the pattern. For n = 10^6 and m = 10^4, that’s 10^10 operations — roughly 30 seconds at 3×10^8 ops/sec. The algorithms in this file reduce that to O(n + m). The key insight behind all of them: use information from previous comparisons to avoid redundant work. KMP does it with a failure function, Z-algorithm does it with a Z-array, Rabin-Karp does it with a rolling hash. Learn all three; KMP first.

---

Why Naive Matching Fails

Text:    AAAAAAAAAB  (9 A's then B)
Pattern: AAAAB       (4 A's then B)

Naive: At each position 0..5, match 4 A's then fail on B.
Total comparisons: 6 * 5 = 30 for n=10, m=5.
In general: O(n*m).

KMP achieves O(n + m) by, upon a mismatch, not restarting from scratch — instead jumping to the longest proper prefix of the matched portion that is also a suffix (hence “failure function”).

---

KMP: Knuth-Morris-Pratt

The Failure Function (LPS Array)

lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix.

“Proper prefix” means not the entire string.

Example: pattern = “ABABC”

i: 0  1  2  3  4
p: A  B  A  B  C
lps: 0  0  1  2  0

• lps[0] = 0: no proper prefix of “A” is also a suffix.

• lps[1] = 0: “AB” — no prefix of “AB” equals a suffix.

• lps[2] = 1: “ABA” — prefix “A” = suffix “A”. Length 1.

• lps[3] = 2: “ABAB” — prefix “AB” = suffix “AB”. Length 2.

• lps[4] = 0: “ABABC” — no proper prefix = suffix.

Why lps matters: When matching fails at pattern[j], you don’t restart from pattern[0]. You restart from pattern[lps[j-1]]. You’ve “already matched” the lps prefix, so you don’t re-examine it.

Building the LPS Array: O(m)

def build_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0    # length of previous longest prefix-suffix
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]   # key: fall back, don't reset i
            else:
                lps[i] = 0
                i += 1
    return lps

The length = lps[length - 1] line is the non-obvious step: when a mismatch occurs at position length, we try the next best candidate (the lps of the shorter prefix), not 0. This is what gives O(m) amortized — length can increase at most m times total, so the fallback chain is bounded by m total steps.

KMP Matching: O(n)

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = build_lps(pattern)
    results = []
    j = 0    # index into pattern
    i = 0    # index into text
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        if j == m:
            results.append(i - j)   # match found at i - j
            j = lps[j - 1]          # look for next match
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]      # fall back in pattern
            else:
                i += 1              # no match at all, advance text
    return results

Worked Example

Pattern: “ABABC”, Text: “ABABDABAABABC”

LPS for “ABABC”: [0, 0, 1, 2, 0]

Matching trace (abbreviated):

• Match “ABAB” (positions 0-3), mismatch at D vs C.

• j = lps[3] = 2 → restart from “AB” already matched.

• Continue from text position 4, pattern position 2.

• Eventually match “ABABC” at position 7 in text.

Without KMP: would have restarted at position 1 in text after first mismatch. KMP saves the “AB” prefix already known to match.

---

Z-Algorithm

The Z-array Z[i] = length of the longest substring starting at s[i] that is also a prefix of s.

Z[0] is undefined (or 0 by convention — the whole string trivially matches itself).

Example: s = “AABXAA”

Z: [-, 1, 0, 0, 2, 1]

Z[4] = 2 because s[4..5] = “AA” = s[0..1].

Building Z-Array: O(n)

def build_z(s):
    n = len(s)
    Z = [0] * n
    l, r = 0, 0    # window [l, r] is the current Z-box
    for i in range(1, n):
        if i < r:
            Z[i] = min(r - i, Z[i - l])   # reuse previous Z values
        while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] > r:
            l, r = i, i + Z[i]
    return Z

The Z-box [l, r] tracks the rightmost matching window found so far. Reusing Z[i - l] prevents recomputing already-known match information.

Pattern Matching with Z-Algorithm

Concatenate: s = pattern + "$" + text (separator ensures pattern chars don’t bleed into text matches).

Build Z-array. Any position i in the text portion (i > m) where Z[i] == m is a match at position i - m - 1 in the original text.

def z_search(text, pattern):
    combined = pattern + "$" + text
    Z = build_z(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if Z[i] == m]

KMP vs. Z-Algorithm

Both are O(n + m). The algorithms are different in structure but equivalent in power.

Z-algorithm is simpler to reason about: Z[i] directly says “how long a prefix matches here.” Less conceptual load than the failure function.

KMP is more expected in interviews: FAANG interviewers reference KMP by name. If asked “how would you do this in O(n+m)?”, say KMP first. Z is acceptable.

CP community: Both are used; choice is personal preference. Most CF editorial solutions mention one or the other without strong preference. The CSES string section accepts either.

---

Rabin-Karp: Rolling Hash

Instead of character-by-character matching, compute a hash of the pattern and roll a window hash across the text. When hashes match, verify with direct comparison (to handle collisions).

Rolling Hash Formula

Treat string as a base-B polynomial:

hash(s[0..m-1]) = s[0]*B^(m-1) + s[1]*B^(m-2) + ... + s[m-1]*B^0   (mod P)

To slide the window by one position (remove s[i], add s[i+m]):

new_hash = (old_hash - s[i] * B^(m-1)) * B + s[i+m]   (mod P)

The B^(m-1) term can be precomputed. Each roll is O(1).

When to Prefer Rabin-Karp over KMP

1. Multiple pattern search: Compute all pattern hashes into a set. Roll one window over text. O(n + total_pattern_length) amortized vs. running KMP for each pattern separately.

2. Find duplicate substrings of length k: Binary search on length + hashing (Rabin-Karp + binary search = O(n log n)). More natural than KMP for this.

3. Anti-hash defense: Use double hashing (two different (B, P) pairs). Probability of collision under two independent hashes is negligible.

Implementation Skeleton

MOD = 10**9 + 7
B = 31   # or any prime > alphabet size

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    # compute powers of B
    power = [1] * (m + 1)
    for i in range(1, m + 1):
        power[i] = power[i-1] * B % MOD
    # compute pattern hash
    ph = 0
    for c in pattern:
        ph = (ph * B + ord(c)) % MOD
    # slide window
    wh = 0
    for i in range(m):
        wh = (wh * B + ord(text[i])) % MOD
    results = []
    for i in range(n - m + 1):
        if wh == ph and text[i:i+m] == pattern:  # verify on hash match
            results.append(i)
        if i + m < n:
            wh = (wh - ord(text[i]) * power[m] % MOD + MOD) % MOD
            wh = (wh * B + ord(text[i + m])) % MOD
    return results

---

Z-Algorithm for Manacher’s Intuition

Manacher’s algorithm finds all palindromic substrings in O(n). The idea mirrors Z-algorithm: maintain a “rightmost palindrome” window and reuse previously computed palindrome lengths to avoid redundant expansion.

Result: For each center c (including between characters for even-length palindromes), P[c] = radius of the longest palindrome centered at c.

The algorithm itself is ~15 lines. Key insight: when center c is inside the current rightmost palindrome window [l, r], we can initialize P[c] using the mirror center mirror = 2*center - c — same “reuse previous computation” idea as Z-algorithm.

Manacher’s use cases: Longest palindromic substring (O(n)), count all distinct palindromic substrings, shortest palindrome by prepending (LeetCode 214).

Full implementation is in cp-algorithms.com/string/manacher. Read it once, implement once, and flag the LeetCode problems it applies to.

---

What Most Engineers Get Wrong

Implementing KMP without understanding the failure function. Most people who “know KMP” have memorized the code. This breaks under two conditions: (1) interview asks them to derive it from scratch, which is common, and (2) novel problems that require modifying the failure function (e.g., “find the shortest period of a string,” which uses lps directly). If you don’t know WHY lps[i] falls back to lps[lps[i-1]-1] instead of 0, you don’t know KMP — you’ve memorized a spell without knowing the incantation.

The test: explain in plain English what j = lps[j-1] does during mismatch. If you can’t, go back and re-derive the failure function from scratch with a worked example.

---

Practice Problems

KMP Applications

1. Find the Index of the First Occurrence in a String — LeetCode 28. The canonical KMP problem. Implement it properly (not text.find(pattern)).

2. Shortest Palindrome — LeetCode 214. KMP application: find the longest palindromic prefix by using KMP failure function on s + "#" + reverse(s).

Rolling Hash

3. Repeated DNA Sequences — LeetCode 187. Rolling hash or sliding window + set. Rolling hash is the elegant solution.

4. Longest Duplicate Substring — LeetCode 1044. Binary search on length + Rabin-Karp rolling hash. Hard — requires careful hash collision handling.

Manacher’s

5. Longest Palindromic Substring — LeetCode 5. O(n) with Manacher’s; O(n²) with expand-around-center. Implement Manacher’s at least once.

6. Palindromic Substrings — LeetCode 647. Count all palindromic substrings. Manacher’s or expand-around-center. Manacher’s is O(n).

---

Navigation

• Previous: 04 — Bit Manipulation

• Next: 06 — Advanced Sorting & Search

• Phase overview: README