String Algorithms — Master Recap and Pattern Cheatsheet

String Algorithms Master Recap#

Complete cheatsheet for all 20 string algorithm problems in this series, with algorithm selection guide and complexity reference.

Problem Index#

Algorithm Selection Guide#

Single pattern search in text?
  → KMP O(n+m) — exact match, worst-case guaranteed
  → Rabin-Karp O(n+m) expected — multiple length patterns
 
All prefix occurrences / repeated substring?
  → Z-algorithm O(n+m)
  → KMP failure function at last position
 
Longest palindromic substring?
  → Manacher O(n) — fastest
  → Expand around center O(n^2) — simpler to implement
 
O(1) substring comparison?
  → Polynomial string hashing with prefix array
 
Lexicographic substring queries (LCP, distinct count)?
  → Suffix array O(n log n) build + O(1) LCP
 
Multi-pattern search?
  → Aho-Corasick O(n + total_pattern_length + z)
 
Edit distance / LCS?
  → Classic DP O(nm), optimize with rolling array to O(n)
 
Count palindromic substrings?
  → Expand O(n^2) or Manacher O(n)

Complexity Summary#

KMP Failure Function Template#

def build_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]   # do NOT increment i here
        else:
            lps[i] = 0
            i += 1
    return lps

Rolling Hash Template#

MOD = (1 << 61) - 1   # Mersenne prime
BASE = 131
 
def build_hash(s):
    n = len(s)
    h = [0] * (n + 1)
    p = [1] * (n + 1)
    for i in range(n):
        h[i+1] = (h[i] * BASE + ord(s[i])) % MOD
        p[i+1] = p[i] * BASE % MOD
    def get(l, r):  # hash of s[l..r] inclusive, 0-indexed
        return (h[r+1] - h[l] * p[r-l+1]) % MOD
    return get

Z-Algorithm Template#

def z_function(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        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

Common Pitfalls#

1. KMP: forgetting j = lps[j-1] on mismatch. The whole point is NOT resetting j to 0.
2. KMP on combined string for Shortest Palindrome: forgetting the # separator. Without it, the LPS bleeds across the boundary.
3. Rolling hash: not using a Mersenne prime modulus. Small primes collide frequently on adversarial inputs.
4. Manacher: mixing 0-indexed and 1-indexed. Insert # separators consistently and never mix conventions.
5. Aho-Corasick: forgetting to propagate output links. Patterns that are suffixes of other patterns will be missed.
6. Suffix array: using naive O(n^2 log n) sort. Build with the O(n log n) doubling approach for large n.

Interview Mindset#

• For single pattern search, KMP is the expected O(n+m) answer. Always explain the failure function, not just the mechanics.
• For palindromes, offer Manacher as the O(n) solution but acknowledge that expanding from center is simpler if Manacher implementation is not required.
• For hashing problems, mention the double-hash technique (two bases/moduli) to reduce collision probability.
• When a problem involves many string queries on the same text, think suffix array or hashing — not repeated KMP.

Key Takeaways#

• KMP achieves O(n+m) by never moving the text pointer backward — the failure function encodes the pattern's self-similarity.
• The Z-array z[i] = length of longest substring starting from s[i] that matches a prefix of s — directly enables pattern search by concatenating pattern + '#' + text.
• Manacher's algorithm computes all palindromic substrings in O(n) by exploiting previously computed palindrome radii to skip redundant checks.
• Rolling hash enables O(1) substring comparison after O(n) preprocessing — use a Mersenne prime modulus to minimize collisions.
• Aho-Corasick extends KMP failure links to a trie, enabling simultaneous O(n + m + z) search for k patterns in a single text pass.
• Suffix arrays solve the hardest substring problems (LCP, distinct substring count, lexicographic ordering) in O(n log n) space and time.
• The right algorithm depends on the query type: single pattern → KMP; multi-pattern → Aho-Corasick; palindromes → Manacher; substring equality → hashing.