the Boyer-Moore algorithm
/ BOY-er MOOR /
Most matching algorithms scan the pattern left to right. Boyer-Moore does something counterintuitive: it aligns the pattern with the text and then compares from the right end of the pattern backward. The payoff is that a single mismatch near the right can let you jump the pattern forward by many characters at once, sometimes skipping over large chunks of text without even looking at them. For long patterns this makes it the fastest exact matcher in practice.
Two rules decide how far to jump after a mismatch, and you take the larger of the two. The bad-character rule: look at the text character that caused the mismatch. If that character does not appear in the pattern at all, you can slide the pattern entirely past it; if it appears, slide so the pattern's rightmost copy of that character lines up under it. The good-suffix rule: if you matched some suffix of the pattern before failing, shift so that another occurrence of that matched suffix (or a prefix of the pattern matching its tail) lines up, much like KMP's failure idea but on suffixes. Both rules are precomputed from the pattern in O(m + alphabet) time. With these, on typical text Boyer-Moore inspects far fewer than n characters — it can run in sublinear time, around O(n/m) comparisons in good cases.
Boyer-Moore, published in 1977, is what your operating system's grep and many editors actually use, often in the simplified bad-character-only form known as Boyer-Moore-Horspool. The honest caveats: its celebrated speed is an average-case, large-alphabet, long-pattern phenomenon; the plain bad-character version still has an O(n*m) worst case (the full Boyer-Moore with the good-suffix rule, and the Galil variant, restore linear worst-case bounds). On tiny alphabets like DNA, the skips shrink and the advantage over KMP narrows. The deep lesson is that scanning right-to-left lets information from the end of the pattern drive big, safe jumps — a different gear from KMP's never-re-read discipline.
P = "NEEDLE" against T = "...XXXXXXNEEDLE...". Align P, compare from the right: P's 'E' vs the text char under it, say 'X'. 'X' is not in "NEEDLE", so the bad-character rule slides the whole pattern past that 'X' — six positions at once, skipping characters never examined. Compare against KMP, which would have read every one of those text characters.
Scanning right-to-left, an absent text character lets Boyer-Moore leap the pattern past it untouched.
The 'sublinear in practice' speed needs a reasonably large alphabet and a longish pattern; on small alphabets or with the bad-character rule alone, the worst case is still O(n*m). Use the good-suffix rule (or the Galil rule) when you need a guaranteed linear bound.