"Every fast string algorithm shares one secret: don't re-compare characters you already know. Naive matching forgets everything after each failure, so it's slow; KMP remembers with a 'failure function', Z with a 'z-box', hashing with a 'prefix'. The whole art is remembering so you never rescan."

This is the ninth grimoire. String processing holds some of the most beautiful — and most bug-prone — algorithms in all of CS. The thread running through it (and through the whole series) is still: don't redo work you've already done. This book teaches four families of weapons: pattern matching (KMP, Z, Rabin-Karp), string hashing, prefix trees (Trie), and symmetry (Manacher).

The core string problems revolve around matching (find a pattern in text), comparing (are two segments equal?), and structure (prefixes, suffixes, symmetry).

What every fast string algorithm has in common: it exploits information it has already learned to avoid re-comparing. Naive matching is the fool — it forgets everything after each failure and starts over. The smart ones remember:

The naive way: try to match the pattern at every position of the text.

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    result = []
    for i in range(n - m + 1):          # try every start position
        if text[i:i+m] == pattern:      # compare the whole pattern
            result.append(i)
    return result

The problem: worst case O(n·m). E.g. text = "aaaa...a", pattern = "aaa...ab" — each position matches almost fully, then fails at the last character, then forgets everything and repeats. Every algorithm below exists to fix exactly this waste.

Part A · Pattern Matching

KMP (Knuth-Morris-Pratt) achieves O(n+m) thanks to the prefix function — which tells you, on a mismatch, where to "jump back" to without rescanning the text.

What is the prefix function?

π[i] = the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. In other words: "the longest head that also matches the tail".

Example for "ababaca":

   pattern:  a  b  a  b  a  c  a
   π:        0  0  1  2  3  0  1
                        ↑
   π[4]=3 because "aba" (prefix) = "aba" (suffix of "ababa")

Computing the prefix function

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]                     # try to extend the previous match
        while j > 0 and s[i] != s[j]:
            j = pi[j-1]                 # ⭐ mismatch → jump back via π
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

Searching with KMP

def kmp_search(text, pattern):
    if not pattern:
        return []
    pi = prefix_function(pattern)
    result, j = [], 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j-1]                 # ⭐ mismatch → jump back, do NOT move i
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):           # full pattern matched
            result.append(i - j + 1)
            j = pi[j-1]                 # keep searching for the next match
    return result

The Z-function is KMP's sibling. z[i] = the length of the longest segment starting at i that matches a prefix of the string.

   s:     a  a  b  c  a  a  b  x  a  a  a  z
   z:     -  1  0  0  3  1  0  0  2  2  1  0
                       ↑
   z[4]=3 because "aab" (starting at 4) = "aab" (prefix)

def z_function(s):
    n = len(s)
    z = [0] * n                         # z[0] left at 0 (convention, usually unused)
    l, r = 0, 0                         # [l, r] = "z-box": rightmost prefix-match segment
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l]) # ⭐ reuse info inside the z-box (mirror)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                   # manually extend the unknown part
        if i + z[i] > r:
            l, r = i, i + z[i]          # update the z-box
    return z

Searching with the Z-function

Concatenate pattern + separator + text, then find positions where z[i] == len(pattern):

def z_search(text, pattern):
    combined = pattern + "\x00" + text   # a separator not present in the input
    z = z_function(combined)
    m = len(pattern)
    result = []
    for i in range(m + 1, len(combined)):
        if z[i] == m:                    # segment at i matches the full pattern
            result.append(i - m - 1)     # convert back to a position in text
    return result

Rabin-Karp turns string matching into number matching: hash the pattern, then slide a "hash window" across the text, updating the hash incrementally (rolling). Average O(n+m).

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n: return []
    BASE, MOD = 256, 10**9 + 7
    p_hash = t_hash = 0
    power = 1                            # BASE^(m-1) % MOD
    for i in range(m):
        p_hash = (p_hash * BASE + ord(pattern[i])) % MOD
        t_hash = (t_hash * BASE + ord(text[i])) % MOD
        if i < m - 1:
            power = (power * BASE) % MOD
    result = []
    for i in range(n - m + 1):
        if p_hash == t_hash:            # ⭐ hash match → verify for REAL (avoid collisions)
            if text[i:i+m] == pattern:
                result.append(i)
        if i < n - m:                   # roll the window: drop first char, add next char
            t_hash = ((t_hash - ord(text[i]) * power) * BASE + ord(text[i+m])) % MOD
            t_hash %= MOD               # ⭐ keep it non-negative
    return result

Quick pick: need a stable, guaranteed matcher → KMP or Z (whichever you know better). Need to compare many substrings or extend flexibly → hashing (Part B).

Part B · String Hashing

The idea: treat a string as a number in a large base. Polynomial hash: hash(s) = s[0]·B^(k-1) + s[1]·B^(k-2) + ... + s[k-1] (mod a large prime). After O(n) preprocessing, compare any two substrings in O(1).

class StringHash:
    def __init__(self, s):
        self.BASE, self.MOD = 131, 10**9 + 7
        n = len(s)
        self.prefix = [0] * (n + 1)     # prefix[i] = hash of s[0..i-1]
        self.power = [1] * (n + 1)      # power[i] = BASE^i
        for i in range(n):
            self.prefix[i+1] = (self.prefix[i] * self.BASE + ord(s[i])) % self.MOD
            self.power[i+1]  = (self.power[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):           # hash of s[l..r] (inclusive) — O(1)
        return (self.prefix[r+1] - self.prefix[l] * self.power[r-l+1]) % self.MOD

Powerful application: O(1) substring comparison unlocks many problems — e.g. combined with binary search to find the "longest common prefix" or "longest palindrome" in O(n log n) (link to Binary Search: binary-search on length + verify with a hash).

Collision: two different strings can share the same hash value. With a MOD of ~10⁹, the random collision probability is small but not zero, and in contests an "anti-hash test" may deliberately break it.

Defenses:

1. Verify the real string on a hash match (perfectly safe, but costs O(m) per match).
2. Double hashing: use two independent (BASE, MOD) pairs; only treat as a match when both hashes agree. Collision probability drops to ~1/MOD², usually safe enough to skip verification.
3. Pick a large prime MOD and a random BASE (defends against crafted tests).

Part C · Trie (Prefix Tree)

A Trie (prefix tree) stores a set of strings by sharing common prefixes — each edge is a character, each root-to-node path is a prefix. Ideal for prefix queries and many patterns.

   Trie holding {"cat", "car", "card", "dog"}:

            (root)
           /      \
          c        d
          |        |
          a        o
         / \       |
        t   r      g*
        *   |
            d*     (* = end of a word)

class TrieNode:
    def __init__(self):
        self.children = {}              # char → TrieNode
        self.is_end = False             # does a word end here?

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):             # is this EXACT word present?
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):      # any word starting with prefix?
        return self._find(prefix) is not None

    def _find(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Complexity: inserting/finding a word of length L is O(L) — independent of how many words are stored. That's the big win when you have many words.

A Trie shines when:

• Autocomplete: type a prefix → walk the subtree to suggest completions.
• Many patterns sharing prefixes: check batches of words efficiently.
• Word Search II (seen in the Backtracking grimoire): pack all words into a Trie, then DFS the grid once, pruning by the Trie — far faster than searching each word separately.
• Maximum XOR (binary Trie): store numbers as bits in a Trie; find the max-XOR pair by greedily "going against each bit".

🔸 Aho-Corasick (advanced — know it so you don't fear it)

Want to find many patterns at once in a text in O(n + Σ|pattern| + matches)? Aho-Corasick = KMP applied to a Trie. It builds a Trie of the patterns, then adds failure links between nodes — exactly KMP's prefix function, but on a tree. Scanning the text, on a mismatch you jump along the failure link. It's the workhorse for keyword filtering and multi-pattern detection (like content filters).

Part D · Symmetry (Palindromes)

Find the longest palindromic substring in O(n) — faster than O(n²) DP. A double trick: (1) insert separators to handle even and odd palindromes uniformly; (2) use mirror symmetry to reuse already-computed results.

def manacher(s):
    if not s: return ""
    # transform "abc" → "^#a#b#c#$": # handles even/odd, ^ and $ are sentinels
    t = "^#" + "#".join(s) + "#$"
    n = len(t)
    p = [0] * n                         # p[i] = palindrome radius at center i
    center = right = 0
    for i in range(1, n - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])   # ⭐ mirror across center
        while t[i + p[i] + 1] == t[i - p[i] - 1]:       # extend the unknown part
            p[i] += 1
        if i + p[i] > right:            # update the rightmost palindrome
            center, right = i, i + p[i]
    max_len, center_index = max((p[i], i) for i in range(n))
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

Common Sections

💀 Pitfall #1 — Using naive when n·m is too large. Long strings + many queries but still text[i:i+m] == pattern in a loop → TLE. Switch to KMP/Z/hashing.

💀 Pitfall #2 — Unverified hash collisions. A hash match does not guarantee a string match. Either verify the real string, or use double hashing.

💀 Pitfall #3 — Overflow / negatives in hashing. In C++/Java, hash multiplication overflows 64-bit → mod after every multiplication. In a rolling hash, after subtraction do +MOD then %MOD to avoid negative values.

💀 Pitfall #4 — Off-by-one in the prefix function / z-box. π and z are extremely prone to off-by-one or mismanaging the [l, r] boundary. Memorize one correct implementation and validate with small examples.

💀 Pitfall #5 — Weak MOD or bad BASE. Small MOD / power of 2 → systematic collisions. Use a large prime + random BASE.

💀 Pitfall #6 — Trie memory bloat. A 26-child array per node wastes space on sparse strings; use a dict for large/sparse alphabets. For a small fixed alphabet, arrays are faster.

💀 Pitfall #7 — Manacher: wrong transform / missing sentinels. Forgetting ^ and $ → manual boundary checks, error-prone. A wrong start = (center - len)//2 extracts the wrong segment.

1. "Don't redo work" — the shared thread. KMP/Z/hashing remember so they never rescan; exactly like two pointers never retreating, DP never recomputing a subproblem.
2. Rolling hash = sliding window. Updating a hash "add in, drop out" is a fixed sliding window (Two Pointers).
3. Prefix hash = prefix sum. O(1) substring hashing is the prefix-sum technique (DP, Two Pointers), just a different operation.
4. Hashing + binary search. Find the longest palindrome / common prefix by binary-searching on length + hash verification (Binary Search).
5. Trie + Backtracking + Bit. Word Search II uses a Trie to prune grid DFS; a binary Trie solves XOR problems. Aho-Corasick = Trie + KMP's failure function.
6. Failure function ~ DP. π and z are built step by step from earlier results — dynamic-programming thinking.

Four questions for any string problem: (1) One pattern or many? (2) Do you need matching, segment comparison, or prefix queries? (3) Is symmetry (palindrome) involved? (4) How large is the string (will naive make it)?

🟢 Level 1 — Intro: Implement strStr() (KMP/Z), Implement Trie (Prefix Tree), Longest Common Prefix, Valid Anagram / Group Anagrams.

🟡 Level 2 — Applied: Repeated Substring Pattern (KMP prefix function), Shortest Palindrome (KMP on s + '#' + reverse(s)), Longest Palindromic Substring (Manacher), Design Add and Search Words (Trie + .), Find All Anagrams in a String (sliding window).

🔴 Level 3 — Advanced: Maximum XOR of Two Numbers (binary Trie), Longest Duplicate Substring (hashing + binary search), Word Search II (Trie + grid DFS), Distinct Echo Substrings (hash segment compare), Palindrome Pairs (Trie/hashing).

⚫ Final boss: Stream of Characters (Aho-Corasick), Number of Matching Subsequences, Suffix Array / Suffix Automaton (self-study). And prove by hand: why the prefix function lets KMP run in O(n).

1. Every fast string algorithm "remembers so it never rescans". KMP with the prefix function, Z with the z-box, hashing with prefixes.
2. KMP: on failure, jump j back, keep the text pointer fixed. The pointer only advances → O(n).
3. Hashing turns string comparison into number comparison — but mind collisions. Prefix hash gives O(1) substring comparison; always verify or double hash.
4. Trie for many patterns & prefix queries. One pattern → KMP; many patterns sharing prefixes → Trie; many patterns on a stream → Aho-Corasick.
5. Longest palindrome → Manacher O(n) (or hashing + binary search if you forget).

Work through all four levels in Part H, ask the four framing questions on each problem, and pick the tool you implement most reliably — after ~30–40 problems, you'll instantly see which problems are matching, which are segment comparison, which need a Trie. That's when you've mastered the art of string processing. 📜