Part 8 · 1 chapters · ~8 min

String Algorithms

Strings as arrays, naive search and KMP, rolling hashes and Rabin-Karp, tries and Aho-Corasick for many patterns, suffix arrays, regular expressions and backtracking blowups (ReDoS), Unicode pitfalls, and string building costs.

Searching text

code

// Rabin-Karp: rolling hash makes each window's hash O(1) from the previous one
function rabinKarp(text: string, pat: string): number[] {
  const B = 256n, M = 1_000_000_007n, m = pat.length, out: number[] = [];
  if (m > text.length) return out;
  let hp = 0n, ht = 0n, pow = 1n;
  for (let i = 0; i < m; i++) { hp = (hp * B + BigInt(pat.charCodeAt(i))) % M; ht = (ht * B + BigInt(text.charCodeAt(i))) % M; if (i) pow = pow * B % M; }
  for (let i = 0; ; i++) {
    if (hp === ht && text.startsWith(pat, i)) out.push(i);             // verify on hash match
    if (i + m >= text.length) break;
    ht = ((ht - BigInt(text.charCodeAt(i)) * pow % M + M) * B + BigInt(text.charCodeAt(i + m))) % M;
  }
  return out;
}

algorithm	complexity	use
naive search	O(n·m) worst	short patterns; often what built-ins do with optimisations
KMP	O(n + m)	never re-reads text; uses a failure table of the pattern
Rabin-Karp	O(n + m) expected	many patterns of equal length, plagiarism and duplicate detection
Aho-Corasick	O(n + matches)	thousands of patterns at once (blocklists, sanctions name screening)
suffix array	O(n log n) build, O(m log n) query	many queries over one large text

Regex danger: backtracking engines (JavaScript, Python, Java, Ruby) can take exponential time on patterns like (a+)+$ against crafted input: ReDoS. Use linear-time engines (RE2, Go and Rust regex) for untrusted input. Unicode: "length" may count UTF-16 units, code points or grapheme clusters; ₦ and emoji break naive slicing (use Intl.Segmenter).