Strings

Strings#

Strings come up everywhere, in search, parsers, bioinformatics, edit distance, fuzzy matching. A handful of algorithms cover most of the ground.

Substring Search#

Find a pattern of length m inside a text of length n, the most common string operation in software. Real-world libraries (str.find, strstr, memmem) typically use Boyer-Moore-Horspool or Two-Way; the choice rarely matters at application level.

Algorithm	Time	Notes
Naive	O(nm)	Two nested loops
Knuth-Morris-Pratt (KMP)	O(n + m)	Builds a prefix function
Boyer-Moore	O(nm) worst	Sublinear in practice
Boyer-Moore-Horspool	Simpler BM	Often the implementation in libs
Rabin-Karp	O(n + m) avg	Hash-based; great for multi-pattern

Real-world libraries (str.find / strstr / memmem) typically use Boyer-Moore-Horspool or Two-Way; the choice rarely matters at application level.

KMP, Failure Function#

KMP precomputes how much of the pattern is a proper prefix that is also a suffix at each position. On a mismatch, it shifts by that much instead of restarting.

The prefix function alone has uses (Z-algorithm equivalent): finding all occurrences of the pattern, computing the longest palindromic prefix, counting distinct palindromes.

Rabin-Karp#

Hash the pattern and rolling-hash the text.

Compare hashes (O(1)) instead of strings.
On hash match, verify by comparing the strings (O(m)).
Polynomial rolling hash with a prime modulus is the standard.

Strengths.

Multiple pattern search, store hashes of all patterns; one pass over the text.
Plagiarism / duplicate detection, shingle the text into hashes.

Tries#

Tree where each edge is a character. Insertion, lookup, and prefix search are all O(m) for a key of length m, crucially independent of dataset size, which is why tries are the right structure for autocomplete, IP routing tables, and dictionary-like workloads.

Insert, lookup, prefix-search in O(m).
Memory-heavy for sparse alphabets.

Used for.

Autocomplete.
IP routing tables (PATRICIA / radix trees).
Spell checkers and dictionaries.
Word break / segmentation.

Suffix Structures#

Pre-process the text once; answer many queries fast. Suffix structures dominate any workload where the same long text gets searched repeatedly, in bioinformatics pipelines (read alignment), full-text indexes, and repeat-finding tools across very large corpora.

Suffix array, sorted array of all suffixes. O(n log² n) or O(n) to build (DC3 / SA-IS).
Suffix automaton, accepts all substrings; O(n) to build.
Suffix tree, compressed trie of all suffixes; O(n) to build (Ukkonen). Memory-heavy.
Generalized suffix structures, over multiple strings.

Applications.

Pattern matching: O(m log n) with binary search on suffix array.
Longest common substring across multiple strings.
Bioinformatics (read alignment, BWA / Bowtie).
Repeated-substring discovery.

Edit Distance#

How many single-character edits (insert / delete / substitute) transform one string into another. The classic O(nm) DP is the foundation of spell-check, fuzzy search, and DNA alignment, enough that the algorithm has variants per use case.

Levenshtein distance, the classic; O(nm) DP.
Damerau-Levenshtein, adds transposition.
Hamming distance, substitutions only; equal-length strings.

DP recurrence.

dp[i][j] = 0                          if i = 0 = j (empty)
         = i                          if j = 0
         = j                          if i = 0
         = dp[i-1][j-1]               if a[i] == b[j]
         = 1 + min(dp[i-1][j],
                   dp[i][j-1],
                   dp[i-1][j-1])      otherwise

Optimizations.

O(n + m) space with rolling rows.
Bit-parallel methods (Myers, Hyyro) for short patterns.

Applications: spell-check, fuzzy search, DNA alignment.

Longest Common Subsequence (LCS)#

Longest sequence appearing in both strings, not necessarily contiguous. O(nm) DP. Foundation of diff.

Longest Common Substring#

Longest contiguous match. O(nm) DP, or O(n + m) with a generalized suffix structure.

Palindromes#

Manacher’s algorithm, O(n) for the longest palindromic substring.
Eertree, palindromic tree; O(n) build, supports many palindrome queries.

Hashing#

The hashing techniques that show up in string algorithms. Rolling hashes power Rabin-Karp; double hashing defends against adversarial collisions; cryptographic hashes fingerprint content for integrity and content-addressable storage.

Rolling hashes, update O(1) when sliding a window. Polynomial hashes are simple and good; Rabin-Karp uses one.
Double hashing, two hash families to lower the collision probability for adversarial inputs.
Cryptographic hashes (SHA-256, BLAKE3), collision-resistant; for fingerprinting, integrity, content-addressable storage.

Regular Expressions#

Two main implementation styles, with different complexity and security stories. Backtracking engines support more features (backreferences, lookaheads); DFA-based engines guarantee linear time and immune themselves to ReDoS, the regex-based denial-of-service attack on backtracking implementations.

Backtracking (PCRE, Python re, Perl, Java Pattern, JavaScript RegExp), flexible, supports backreferences and lookarounds; can have catastrophic backtracking.
NFA / DFA based (RE2, Hyperscan, Rust regex), O(n) per match; no backreferences; immune to ReDoS.

For untrusted input, prefer DFA-style engines.

Approximate / Fuzzy Matching#

When exact match isn’t enough (typo tolerance, near- duplicate detection, similarity search), approximate matching fills the gap. Each technique below addresses a specific scale of workload, from per-query (Levenshtein automata) to billion-document corpus (MinHash + LSH).

Levenshtein automata, finite automaton accepting strings within edit distance k.
BK-trees, metric-tree-based.
MinHash + LSH, approximate Jaccard similarity at scale.
Trigram indexes, the basis of Postgres pg_trgm fuzzy search.

Encoding-Aware Considerations#

String algorithms over Unicode text need more care than English-only assumptions allow. The three concerns below come up in any production text-processing system; ignoring them leads to bugs that survive years before someone with the wrong locale or character set finds them.

UTF-8, variable-length; string.length in many languages reports code units, not characters. Iterating Unicode requires care.
Normalization, é can be one code point or two (NFC vs. NFD). Compare and search normalized forms.
Case folding, locale-dependent; Turkish i is the famous edge case.

Most string algorithms above are alphabet-aware; production code on Unicode text needs a Unicode-aware library.

What to Reach For#

The decision flow for “I have a string problem, which algorithm fits?” Match the question to the answer; everything else here is supporting detail for understanding why a given answer is right.

Substring search → language built-in.
Multi-pattern search → Aho-Corasick or Rabin-Karp.
Approximate match within k edits → Levenshtein or fuzzy library.
Many queries on the same text → suffix array / automaton.
Diff between two files → LCS-based (diff, git diff, difflib).