Algorithms · Cluster
String Algorithms
Pattern matching, suffix structures, and text compression.
- 01 The Prefix Function and Linear-Time Exact Matching How the prefix function records the longest proper border of each pattern prefix, and why following failure links keeps total matching work linear in the text length.
- 02 Polynomial Rolling Hashes and the Rabin-Karp Trade How a rolling hash compares substrings in constant time, why collision probability depends on the modulus, and which arithmetic choices fail under adversarial input.
- 03 Right-to-Left Scanning and the Boyer-Moore Shift Tables How comparing the pattern from its end lets a matcher skip whole alignments, what the bad-character and good-suffix tables each guarantee, and where the two rules disagree about the shift.
- 04 Aho–Corasick Failure Links and Multi-Pattern Scanning Why a trie of patterns needs a second set of edges, how the failure link of a node is derived from its parent, and what output propagation costs when patterns nest.
- 05 Suffix Arrays, Prefix Doubling, and the Kasai LCP Scan How sorting all suffixes of a text supports substring queries with one integer array, why doubling sorts in O(n log n), and how the LCP array is computed in a single pass.
- 06 Suffix Automata and Counting Distinct Substrings Online How a suffix automaton stores every substring of a text in linear states, why cloning a state preserves end-position sets, and how the state graph yields the distinct-substring count.
- 07 The Burrows–Wheeler Transform and Backward Search in the FM-Index Why sorting cyclic rotations clusters equal characters, how the LF mapping inverts the transform, and how the same mapping turns the last column into a searchable index.
- 08 Bit-Parallel Approximate Matching with Packed DP Rows How a whole column of the edit-distance table fits into one machine word, what the bit-vector recurrence computes, and where the 64-character pattern limit forces blocking.
- 09 LZ77 and LZ78 Parsing: Offsets Versus a Phrase Dictionary How a sliding window turns repetition into (distance, length) pairs, why LZ78 replaces the window with an explicit phrase table, and what each costs at decode time.
- 10 Lyndon Factorization and the Structure of Minimal Rotations How Duval splits any word into a non-increasing sequence of Lyndon words in linear time, why the longest Lyndon prefix equals the next smaller suffix, and how that decides the smallest rotation.