Morris-Pratt algorithm in Python
Historical precursor of KMP with a weaker failure rule; linear time.
- File
morris_pratt.py, 49 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/morris-pratt/. The authors are listed in prov/SGQC43.jsonl.
from collections.abc import Sequence
from typing import TypeVar
T = TypeVar("T")
def compute_prefix_function(p: Sequence[T]) -> list[int]:
"""Return pi, where pi[q] is the length of the longest proper border of p[:q+1].
Time O(m), at most 2(m - 1) equality tests.
"""
m = len(p) # @line L12
pi = [0] * m
k = 0 # @line L12
for q in range(1, m): # @line L13
while k > 0 and p[k] != p[q]: # @line L14
k = pi[k - 1] # @line L15
if p[k] == p[q]: # @line L16
k += 1
pi[q] = k # @line L17
return pi # @line L18
def morris_pratt(text: Sequence[T], pattern: Sequence[T]) -> list[int]:
"""Return every 0-based shift s with text[s:s+m] == pattern, in increasing order.
General alphabet (only equality tests). Occurrences may overlap. The empty
pattern occurs at each shift 0..n; a pattern longer than the text has none.
Time O(n + m), at most 2n comparisons in the search; extra space O(m).
"""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
return list(range(n + 1))
pi = compute_prefix_function(pattern) # @line L3
out: list[int] = []
q = 0 # @line L4
for i in range(n): # @line L5
c = text[i]
while q > 0 and pattern[q] != c: # @line L6
q = pi[q - 1] # @line L7
if pattern[q] == c: # @line L8
q += 1
if q == m: # @line L9
out.append(i - m + 1) # @line L10
q = pi[m - 1] # @line L11
return out
test_morris_pratt.py 50 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/morris-pratt/. The authors are listed in prov/SGQC43.jsonl.
import random
from morris_pratt import compute_prefix_function, morris_pratt
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 border_oracle(p: str) -> list[int]:
return [max(k for k in range(q + 1) if p[:k] == p[q + 1 - k : q + 1]) for q in range(len(p))]
def test_example() -> None:
assert compute_prefix_function("abacabab") == [0, 0, 1, 0, 1, 2, 3, 2]
assert morris_pratt("abacabcabacababa", "abacabab") == [7]
def test_edges() -> None:
assert morris_pratt("abc", "") == [0, 1, 2, 3]
assert morris_pratt("", "") == [0]
assert morris_pratt("", "a") == []
assert morris_pratt("ab", "abc") == []
assert morris_pratt("a" * 10, "a" * 4) == list(range(7))
assert morris_pratt("a" * 10, "aaab") == []
def test_overlap_after_match() -> None:
assert morris_pratt("abababab", "abab") == [0, 2, 4]
assert morris_pratt("aaaaa", "aa") == [0, 1, 2, 3]
def test_prefix_function_against_definition() -> None:
rng = random.Random(31)
for alphabet in ("a", "ab", "abcd"):
for _ in range(300):
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(1, 12)))
assert compute_prefix_function(p) == border_oracle(p)
def test_random_against_oracle() -> None:
rng = random.Random(1970)
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 morris_pratt(t, p) == oracle(t, p)
What the next level needs
- the tests did not run in this build