String Algorithms — Master Recap and Pattern Cheatsheet

00 — Complete Guide (6 patterns, complexity table)
01 — KMP Search         → failure function O(n+m)
02 — Z-Algorithm        → Z-array O(n+m)
03 — Rabin-Karp         → rolling hash O(n+m) avg
04 — Manacher's         → palindrome O(n)
05 — String Hashing     → O(1) substring compare
06 — Suffix Array       → O(n log²n) build
07 — Longest Common Substring → DP O(nm)
08 — String DP          → edit distance, LCS, interleave
09 — Anagram Problems   → freq vector, sliding window
10 — Palindrome Suite   → expand, DP, min-cut
11 — Word Search I/II   → DFS + Trie
12 — Encode/Decode      → length-prefix
13 — Shortest Palindrome→ KMP on s+'#'+rev
14 — Distinct Substrings→ suffix array + LCP
15 — String Compression → run-length, decode
16 — Trie Advanced      → XOR trie, palindrome pairs
17 — Meta/Google Strings→ longest no-repeat, valid parens
18 — Aho-Corasick       → multi-pattern O(n+m+z)
19 — Master Recap       → this file

Single pattern search?
  → KMP O(n+m) — exact match
  → Rabin-Karp — multiple patterns, expected O(n)

All prefix occurrences?
  → Z-algorithm O(n+m)

Longest palindrome?
  → Manacher O(n) — fastest
  → Expand around centre O(n²) — simpler

Substring comparison O(1)?
  → String hashing with prefix array

Substring queries (LCP, count distinct)?
  → Suffix array O(n log n) build + O(1) LCP

Multi-pattern search?
  → Aho-Corasick O(n + Σm + z)

Edit distance / LCS?
  → Classic DP O(nm), optimise with rolling array

Count palindromic substrings?
  → Expand O(n²) or Manacher O(n)