Boyer-Moore scans the pattern right to left. Two precomputed shift rules — the bad character table and the good suffix table — let it skip large chunks of the text on a mismatch, delivering the famous sub-linear O(n/m) best case. Type a text and pattern, then step through the search.
The bad character rule uses the mismatched text character to shift the pattern past its rightmost occurrence in the pattern. The good suffix rule shifts based on the matched suffix's next occurrence (or its longest border). Boyer-Moore takes max of the two per mismatch.
gs[j] after mismatch at pattern index j)
Published in 1977 by Robert S. Boyer and J Strother Moore, the algorithm's key insight is that comparing the pattern to the text right to left lets a single mismatch produce a much larger safe shift than left-to-right scanning ever could. The bad character heuristic, on a mismatch at pattern index j against text character c, aligns c with its rightmost occurrence in the pattern to the left of j — or shifts entirely past the current window if c doesn't appear. The good suffix heuristic accounts for the already-matched suffix: if that suffix recurs elsewhere in the pattern we align to it, otherwise we shift by the longest prefix that is also a suffix. The GNU grep command has used a Boyer-Moore variant for its literal-string path since the 1980s — its ability to skip most of the text is why grep feels so fast.