Naive string matching in Python
Try every shift and compare; O(nm) worst case.
- File
naive_string_matching.py, 26 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/naive-string-matching/. The authors are listed in prov/NM14X8.jsonl.
from collections.abc import Sequence
from typing import TypeVar
T = TypeVar("T")
def naive_string_matching(text: Sequence[T], pattern: Sequence[T]) -> list[int]:
"""Return every 0-based shift s with text[s:s+m] == pattern, in increasing order.
Characters are compared only for equality, so any sequence of comparable
items works (a general alphabet). Occurrences may overlap. The empty
pattern occurs at each shift 0..n. A pattern longer than the text has no
occurrence. Time O((n - m + 1) m), extra space O(1) besides the output.
"""
n, m = len(text), len(pattern) # @line L1
out: list[int] = []
for s in range(n - m + 1): # @line L2
j = 0 # @line L3
while j < m and text[s + j] == pattern[j]: # @line L4
j += 1 # @line L5
if j == m: # @line L6
out.append(s)
return out
test_naive_string_matching.py 49 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/naive-string-matching/. The authors are listed in prov/NM14X8.jsonl.
import random
from naive_string_matching import naive_string_matching
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 naive_string_matching("abaababaab", "abab") == [3]
assert naive_string_matching("abracadabra", "abra") == [0, 7]
def test_edges() -> None:
assert naive_string_matching("abc", "") == [0, 1, 2, 3]
assert naive_string_matching("", "") == [0]
assert naive_string_matching("", "a") == []
assert naive_string_matching("ab", "abc") == []
assert naive_string_matching("abc", "abc") == [0]
assert naive_string_matching("a" * 10, "a" * 4) == list(range(7))
assert naive_string_matching("a" * 10, "aaab") == []
def test_last_shift() -> None:
# the loop bound must include s = n - m
assert naive_string_matching("xxab", "ab") == [2]
def test_lists() -> None:
assert naive_string_matching([1, 2, 1, 2, 1], [1, 2, 1]) == [0, 2]
def test_random_against_oracle() -> None:
rng = random.Random(4101)
for alphabet in ("a", "ab", "abcd"):
for _ in range(700):
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 30)))
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 6)))
assert naive_string_matching(t, p) == oracle(t, p)
def test_periodic() -> None:
for n in range(12):
for m in range(n + 3):
assert naive_string_matching("a" * n, "a" * m) == (list(range(n - m + 1)) if m <= n else [])
What the next level needs
- the tests did not run in this build