Signal search

Naive search lines the pattern up under every position of the haystack and compares left to right. On a mismatch it throws away everything it just learned, slides one place and starts the pattern again.

Knuth, Morris and Pratt noticed that the characters already matched are the pattern itself, so you can work out ahead of time where to carry on. The partial match table pi records, for each prefix of the pattern, the longest piece that is both a proper prefix and a suffix of it. On a mismatch KMP jumps back to j = pi[j - 1] and never moves backwards in the haystack.

On random DNA the two are close. On a sea of a's with aaaab, naive re-reads almost the whole pattern at every position, while KMP keeps going.

Boyer-Moore compares from the right end of the pattern and, on a mismatch, skips ahead by the larger of two rules. Bad character: slide until the text character that failed lines up with its last copy in the pattern, or jump right past it if it is not in the pattern at all. Good suffix: slide until the part that already matched lines up with another copy of itself. With a long pattern and a varied alphabet it often reads fewer characters than the text has.

Rabin-Karp turns each window of m characters into a number, a hash mod a prime q, and only compares characters when the window's hash equals the pattern's. Rolling the window one place updates the hash in constant time. With a small q different windows share a hash by chance: those spurious hits cost a check and are counted.

The regex engine compiles the pattern with Thompson's construction: each piece becomes a small machine with one way in and dangling ways out, and | , * , + and ? are wired from split states with free (ε) moves. Instead of backtracking it tracks the set of all states the machine could be in, so each character costs at most one step per state.

A tiny table built from the pattern alone turns every failure into information, so the haystack is read once.