Tag
string-matching
- Aug 19, 2026 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. algorithms
- Jul 24, 2026 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. algorithms
- Jan 21, 2026 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. algorithms
- Mar 28, 2023 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. algorithms
- Jul 2, 2022 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. algorithms