Shift-Or algorithm in Python
Bit-parallel matching: a machine word tracks all partial matches; O(n ceil(m/w)) time.
- File
shift_or.py, 34 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/shift-or/. The authors are listed in prov/D9WFTK.jsonl.
from collections.abc import Hashable, Sequence
def shift_or_masks(pattern: Sequence[Hashable]) -> tuple[dict, int]:
"""B[c] has bit j cleared exactly when pattern[j] == c; absent characters use all ones."""
m = len(pattern)
ones = (1 << m) - 1
masks = {} # @line L3
for j, c in enumerate(pattern): # @line L4
masks[c] = masks.get(c, ones) & ~(1 << j)
return masks, ones
def shift_or(text: Sequence[Hashable], pattern: Sequence[Hashable]) -> list[int]:
"""All shifts s with text[s:s+m] == pattern, in increasing order.
Python integers have no fixed width, so one integer plays the role of the
ceil(m / w) machine words of the analysis.
"""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
return list(range(n + 1))
masks, ones = shift_or_masks(pattern)
top = 1 << (m - 1)
state = ones # @line L5
out = []
for i in range(n): # @line L6
state = ((state << 1) | masks.get(text[i], ones)) & ones # @line L7
if not state & top: # @line L8
out.append(i - m + 1)
return out
test_shift_or.py 43 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/shift-or/. The authors are listed in prov/D9WFTK.jsonl.
import random
from shift_or import shift_or, shift_or_masks
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:
masks, ones = shift_or_masks("abab")
assert ones == 0b1111
assert masks == {"a": 0b1010, "b": 0b0101}
assert shift_or("aababab", "abab") == [1, 3]
def test_long_pattern() -> None:
# Longer than a 64-bit word: Python integers grow as needed.
p = "ab" * 50 + "c"
t = "ab" * 120 + "c" + "ab" * 50 + "c"
assert shift_or(t, p) == oracle(t, p)
def test_edges() -> None:
assert shift_or("abc", "") == [0, 1, 2, 3]
assert shift_or("", "") == [0]
assert shift_or("", "a") == []
assert shift_or("ab", "abc") == []
assert shift_or("a" * 10, "a" * 4) == list(range(7))
assert shift_or("a" * 10, "aaab") == []
assert shift_or("xyz", "y") == [1]
def test_random_against_oracle() -> None:
rng = random.Random(1992)
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 shift_or(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build