Boyer-Moore-Horspool algorithm in Python
Simplified Boyer-Moore using only the bad-character rule on the last text character of the window.
- File
boyer_moore_horspool.py, 31 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/boyer-moore-horspool/. The authors are listed in prov/RFB4V2.jsonl.
from collections.abc import Hashable, Sequence
def horspool_shift(pattern: Sequence[Hashable]) -> dict:
"""shift[c] = m - 1 - (last position of c in pattern[:m-1]); absent characters shift by m."""
m = len(pattern)
shift = {} # @line L3
for k in range(m - 1): # @line L4
shift[pattern[k]] = m - 1 - k
return shift
def boyer_moore_horspool(text: Sequence[Hashable], pattern: Sequence[Hashable]) -> list[int]:
"""All shifts s with text[s:s+m] == pattern, in increasing order."""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
return list(range(n + 1))
shift = horspool_shift(pattern)
out = []
s = 0 # @line L5
while s <= n - m: # @line L6
j = m - 1 # @line L7
while j >= 0 and pattern[j] == text[s + j]: # @line L8
j -= 1
if j < 0: # @line L9
out.append(s)
s += shift.get(text[s + m - 1], m) # @line L10
return out
test_boyer_moore_horspool.py 39 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/boyer-moore-horspool/. The authors are listed in prov/RFB4V2.jsonl.
import random
from boyer_moore_horspool import boyer_moore_horspool, horspool_shift
def oracle(t: str, p: str) -> list[int]:
return [s for s in range(len(t) - len(p) + 1) if t.startswith(p, s)]
def test_example() -> None:
assert horspool_shift("gcagagag") == {"g": 2, "c": 6, "a": 1}
assert boyer_moore_horspool("gcatcgcagagagtatacagtacg", "gcagagag") == [5]
def test_last_character_excluded() -> None:
# The last pattern character must not set its own shift to 0.
assert horspool_shift("ab") == {"a": 1}
assert boyer_moore_horspool("abab", "ab") == [0, 2]
def test_edges() -> None:
assert boyer_moore_horspool("abc", "") == [0, 1, 2, 3]
assert boyer_moore_horspool("", "") == [0]
assert boyer_moore_horspool("", "a") == []
assert boyer_moore_horspool("ab", "abc") == []
assert boyer_moore_horspool("a" * 10, "a" * 4) == list(range(7))
assert boyer_moore_horspool("a" * 10, "baaa") == []
def test_random_against_oracle() -> None:
rng = random.Random(1980)
for alphabet in ("a", "ab", "abcd"):
for _ in range(700):
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 40)))
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 7)))
assert boyer_moore_horspool(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build