Boyer-Moore

Compares the pattern to the text right-to-left. A mismatch lets it skip ahead using the bad-character rule — align the mismatched text character with its last occurrence in the pattern — often skipping most of the text.

Category: Strings
Time complexity: O(n/m) best, O(nm) worst
Space complexity: O(alphabet)

Pseudocode

precompute last occurrence of each char in pattern
align pattern at shift s, compare right to left
on mismatch: jump using the bad-character table
match when the whole pattern compares equal

Reference implementation

last = {ch: i for i, ch in enumerate(pat)}
while s + m &lt;= n:
    j = m - 1
    while j &gt;= 0 and pat[j] == text[s+j]: j -= 1
    if j &lt; 0: return s
    s += max(1, j - last.get(text[s+j], -1))

Open the interactive Boyer-Moore visualisation →