Quick Search algorithm in Python
Boyer-Moore variant that uses the character just after the window for the shift.
- File
quick_search.py, 33 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/quick-search/. The authors are listed in prov/GYWS8F.jsonl.
from collections.abc import Hashable, Sequence
def quick_search_shift(pattern: Sequence[Hashable]) -> dict:
"""qs[c] = m - (last position of c in pattern); absent characters shift by m + 1."""
m = len(pattern)
qs = {} # @line L3
for k in range(m): # @line L4
qs[pattern[k]] = m - k
return qs
def quick_search(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))
qs = quick_search_shift(pattern)
out = []
s = 0 # @line L5
while s <= n - m: # @line L6
j = 0 # @line L7
while j < m and pattern[j] == text[s + j]: # @line L8
j += 1
if j == m: # @line L9
out.append(s)
if s + m == n: # @line L10
break
s += qs.get(text[s + m], m + 1) # @line L11
return out
test_quick_search.py 39 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/quick-search/. The authors are listed in prov/GYWS8F.jsonl.
import random
from quick_search import quick_search, quick_search_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 quick_search_shift("gcagagag") == {"g": 1, "c": 7, "a": 2}
assert quick_search("gcatcgcagagagtatacagtacg", "gcagagag") == [5]
def test_window_at_the_end() -> None:
# The last window has no character after it; reading T[n] would fail.
assert quick_search("xxab", "ab") == [2]
assert quick_search("ab", "ab") == [0]
def test_edges() -> None:
assert quick_search("abc", "") == [0, 1, 2, 3]
assert quick_search("", "") == [0]
assert quick_search("", "a") == []
assert quick_search("ab", "abc") == []
assert quick_search("a" * 10, "a" * 4) == list(range(7))
assert quick_search("a" * 10, "aaab") == []
def test_random_against_oracle() -> None:
rng = random.Random(1990)
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 quick_search(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build