Pattern Matching and Preprocessing¶

Preprocessing the pattern (rather than the text) enables sublinear search by precomputing where to resume matching after mismatches, avoiding redundant character comparisons.

Tension Addressed¶

Time vs. Space (preprocessing builds auxiliary structure to speed search)

Recognizable As¶

Failure functions (KMP), bad character rules (Boyer-Moore), finite automata construction; O(n+m) vs. naive O(nm).

Canonical Sources¶

Knuth-Morris-Pratt, "Fast Pattern Matching in Strings," 1977; Boyer-Moore, "A Fast String Searching Algorithm," 1977

Transfers To¶

Text editors, intrusion detection, bioinformatics (genome search), regular expression engines, data compression

The insight generalizes: investing computation upfront on the smaller/reused input (pattern, index, filter) amortizes across many uses of the larger/varying input (text, queries, data stream).