Boyer-Moore algorithm in Python
Compares the pattern right to left and skips using bad-character and good-suffix shifts; sublinear on average.
- File
boyer_moore.py, 68 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/. The authors are listed in prov/GBSH7D.jsonl.
from collections.abc import Hashable, Sequence
def suffixes(p: Sequence[Hashable]) -> list[int]:
"""suff[i] = length of the longest common suffix of p[:i+1] and p, in O(m) time."""
m = len(p)
suff = [0] * m
if m == 0:
return suff
suff[m - 1] = m
g = f = m - 1
for i in range(m - 2, -1, -1):
if i > g and suff[i + m - 1 - f] < i - g:
suff[i] = suff[i + m - 1 - f]
else:
g = min(g, i)
f = i
while g >= 0 and p[g] == p[g + m - 1 - f]:
g -= 1
suff[i] = f - g
return suff
def last_occurrence(p: Sequence[Hashable]) -> dict:
lam = {} # @line L13
for k, c in enumerate(p):
lam[c] = k
return lam
def good_suffix(p: Sequence[Hashable]) -> list[int]:
"""gs[j] = strong good-suffix shift after a mismatch at j; gs[0] is also the period."""
m = len(p)
suff = suffixes(p) # @line L14
gs = [m] * m # @line L15
j = 0
for i in range(m - 1, -1, -1): # @line L16
if suff[i] == i + 1: # @line L17
while j < m - 1 - i: # @line L18
if gs[j] == m: # @line L19
gs[j] = m - 1 - i
j += 1 # @line L20
for i in range(m - 1): # @line L21
gs[m - 1 - suff[i]] = m - 1 - i # @line L22
return gs # @line L23
def boyer_moore(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))
lam, gs = last_occurrence(pattern), good_suffix(pattern) # @line L3
out = []
s = 0 # @line L4
while s <= n - m: # @line L5
j = m - 1 # @line L6
while j >= 0 and pattern[j] == text[s + j]: # @line L7
j -= 1 # @line L8
if j < 0: # @line L9
out.append(s) # @line L10
s += gs[0] # @line L11
else:
s += max(gs[j], j - lam.get(text[s + j], -1)) # @line L12
return out
test_boyer_moore.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/boyer-moore/. The authors are listed in prov/GBSH7D.jsonl.
import random
from boyer_moore import boyer_moore, good_suffix, last_occurrence, suffixes
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 gs_oracle(p: str) -> list[int]:
m, out = len(p), []
for j in range(m):
d = 1
while not (
all(p[i - d] == p[i] for i in range(max(j + 1, d), m)) and (j - d < 0 or p[j - d] != p[j])
):
d += 1
out.append(d)
return out
def period(p: str) -> int:
return next(d for d in range(1, len(p) + 1) if all(p[i - d] == p[i] for i in range(d, len(p))))
def test_example() -> None:
p = "gcagagag"
assert suffixes(p) == [1, 0, 0, 2, 0, 4, 0, 8]
assert good_suffix(p) == [7, 7, 7, 2, 7, 4, 7, 1]
assert last_occurrence(p) == {"g": 7, "c": 1, "a": 6}
assert boyer_moore("gcatcgcagagagtatacagtacg", p) == [5]
def test_edges() -> None:
assert boyer_moore("abc", "") == [0, 1, 2, 3]
assert boyer_moore("", "") == [0]
assert boyer_moore("", "a") == []
assert boyer_moore("ab", "abc") == []
assert boyer_moore("a" * 10, "a" * 4) == list(range(7))
assert boyer_moore("a" * 10, "baaa") == []
def test_tables_against_definition() -> None:
rng = random.Random(77)
for alphabet in ("a", "ab", "abcd"):
for _ in range(400):
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(1, 10)))
gs = good_suffix(p)
assert gs == gs_oracle(p)
assert gs[0] == period(p)
def test_random_against_oracle() -> None:
rng = random.Random(1977)
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(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build