Pattern-Matching Workbench

Workbench Contract and Exact Oracle

Every matcher accepts Unicode strings text and pattern and returns sorted, zero-based starts, including overlaps. The empty pattern matches all $n+1$ boundaries; a pattern longer than the text has no matches. A short $O(nm)$ baseline checks every alignment and serves as the independent correctness oracle.

Instrumentation is separate from results. Preprocessing tables, comparisons, shifts, fallbacks, hash collisions, and bit states belong in trace events so enabling visualization never changes the answer.

Every registered matcher must return exactly the naive oracle’s sorted overlapping positions, including empty and oversized patterns. Probabilistic filters may skip work, but an exact matcher must verify every reported hash candidate.

Algorithm Implementations

The registry below exposes naive, KMP, Z, verified Rabin-Karp, Horspool, Shift-And, and an optimized runtime adapter through one contract. The adapter is named runtime because an interpreter may select Two-Way or another internal strategy; a portable Two-Way implementation should be registered only with independent critical-factorization tests.

from collections.abc import Callable, Sequence
from random import Random

Matcher = Callable[[str, str], list[int]]


def special(text: str, pattern: str) -> list[int] | None:
    if pattern == "":
        return list(range(len(text) + 1))
    if len(pattern) > len(text):
        return []
    return None


def naive(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    m = len(pattern)
    return [i for i in range(len(text) - m + 1) if text[i:i + m] == pattern]


def prefix_function(pattern: str) -> list[int]:
    pi = [0] * len(pattern)
    for i in range(1, len(pattern)):
        border = pi[i - 1]
        while border and pattern[i] != pattern[border]:
            border = pi[border - 1]
        if pattern[i] == pattern[border]:
            border += 1
        pi[i] = border
    return pi


def kmp(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    pi, matched, answer = prefix_function(pattern), 0, []
    for index, symbol in enumerate(text):
        while matched and symbol != pattern[matched]:
            matched = pi[matched - 1]
        if symbol == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            answer.append(index - len(pattern) + 1)
            matched = pi[matched - 1]
    return answer


def z_array(sequence: Sequence[object]) -> list[int]:
    z = [0] * len(sequence)
    left = right = 0
    for i in range(1, len(sequence)):
        if i < right:
            z[i] = min(right - i, z[i - left])
        while i + z[i] < len(sequence) and sequence[z[i]] == sequence[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z


def z_search(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    joined: list[object] = list(pattern) + [object()] + list(text)
    values = z_array(joined)
    offset = len(pattern) + 1
    return [i - offset for i in range(offset, len(joined)) if values[i] >= len(pattern)]


def rabin_karp(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    base, modulus, m = 911_382_323, 1_000_000_007, len(pattern)
    high = pow(base, m - 1, modulus)
    ph = wh = 0
    for i in range(m):
        ph = (ph * base + ord(pattern[i]) + 1) % modulus
        wh = (wh * base + ord(text[i]) + 1) % modulus
    answer = []
    for start in range(len(text) - m + 1):
        if wh == ph and text[start:start + m] == pattern:
            answer.append(start)
        if start + m < len(text):
            wh = (wh - (ord(text[start]) + 1) * high) % modulus
            wh = (wh * base + ord(text[start + m]) + 1) % modulus
    return answer


def horspool(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    m = len(pattern)
    shifts = {c: m - 1 - i for i, c in enumerate(pattern[:-1])}
    answer, start = [], 0
    while start <= len(text) - m:
        i = m - 1
        while i >= 0 and pattern[i] == text[start + i]:
            i -= 1
        if i < 0:
            answer.append(start)
        start += shifts.get(text[start + m - 1], m)
    return answer


def shift_and(text: str, pattern: str) -> list[int]:
    result = special(text, pattern)
    if result is not None:
        return result
    masks: dict[str, int] = {}
    for i, c in enumerate(pattern):
        masks[c] = masks.get(c, 0) | 1 << i
    state, accept, answer = 0, 1 << (len(pattern) - 1), []
    for i, c in enumerate(text):
        state = ((state << 1) | 1) & masks.get(c, 0)
        if state & accept:
            answer.append(i - len(pattern) + 1)
    return answer


def runtime(text: str, pattern: str) -> list[int]:
    if pattern == "":
        return list(range(len(text) + 1))
    answer, start = [], 0
    while True:
        match = text.find(pattern, start)
        if match < 0:
            return answer
        answer.append(match)
        start = match + 1


MATCHERS: dict[str, Matcher] = {
    "naive": naive, "kmp": kmp, "z": z_search,
    "rabin-karp": rabin_karp, "horspool": horspool,
    "shift-and": shift_and, "runtime": runtime,
}


def verify(text: str, pattern: str) -> None:
    expected = naive(text, pattern)
    for name, matcher in MATCHERS.items():
        actual = matcher(text, pattern)
        assert actual == expected, (name, text, pattern, expected, actual)


if __name__ == "__main__":
    for case in [
        ("", ""), ("abc", ""), ("", "a"), ("aaaaa", "aa"),
        ("abracadabra", "abra"), ("abc", "abcd"),
        ("😀a😀a", "😀a"), ("ababababac", "ababac"),
    ]:
        verify(*case)
    random = Random(20260918)
    for _ in range(1_000):
        text = "".join(random.choice("abc") for _ in range(random.randrange(30)))
        pattern = "".join(random.choice("abc") for _ in range(random.randrange(10)))
        verify(text, pattern)

Preprocessing and Scan Visualizations

A synchronized trace separates immutable preprocessing from scan state. KMP exposes prefix values and border length; Z shows its active box; Rabin-Karp shows rolling hashes and verification; Horspool shows the mismatch and chosen shift; Shift-And shows masks, state, and accepting bit. Each event retains shared alignment and action fields plus an algorithm-specific payload.

Correctness and Differential Testing

Differential tests send each generated case to every matcher and compare with the naive oracle. Record the seed, inputs, preprocessing state, and trace prefix on failure. Combine random alphabets and Unicode with adversarial periodic strings, long near-misses, empty inputs, word-boundary pattern lengths, and intentionally collision-prone Rabin-Karp configurations.

Metamorphic properties add coverage: prefixing text and expected positions by a symbol shifts old matches; appending a symbol absent from the pattern cannot create an earlier occurrence; duplicating text preserves matches inside each copy aside from new boundary-spanning matches.

Testing Lab

Debug the Matcher

Use text ababababac and pattern ababac. The correct prefix table is [0,0,1,2,3,0], and the sole match begins at index 4. Corrupt the final entry to 3. A first-match test can still pass, but after a report the matcher resumes with a nonexistent border.

Check the table invariant pattern[:pi[i]] == pattern[i-pi[i]+1:i+1]. At index 5, prefix aba differs from suffix bac, exposing the defect. Recompute from pi[4]=3: c mismatches twice along the fallback chain and reaches zero. Restore pi[5]=0, then rerun overlapping and back-to-back cases. Output tests alone can miss bad preprocessing states, so validate table invariants independently.

Benchmark Report

Benchmark only verified implementations. Separate preprocessing, scanning, and end-to-end time; warm up the runtime, randomize algorithm order, repeat trials, and report medians with environment metadata. Record comparisons, fallbacks, shifts, hash hits, verified collisions, processed words, output size, and peak memory alongside throughput.

The matrix below defines reproducible regimes rather than inventing machine-dependent timings. Populate timing columns by running the harness on the target runtime.

Corpus regime	Construction	Match density	Primary metric	Expected diagnostic result	Algorithms favored
Random large alphabet	$n=1{,}000{,}000$, $m=32$, 64 symbols	Near zero	Throughput and comparisons per byte	Late mismatches permit large shifts	Horspool or runtime
Repetitive near-miss	`a` repeated then `b`; pattern ends in `c`	Zero	Comparisons and fallbacks	Naive repeats work; prefix methods remain linear	KMP, Z, or runtime
Dense overlaps	Text and pattern both all `a`	$n-m+1$	Output throughput	Reporting dominates	KMP, Shift-And, or runtime
Periodic text	Repeated `ab`; pattern ends in `ac`	Low	Shift and fallback distribution	Period structure stresses reuse	KMP, Z, or runtime
Short pattern	$m\le64$ over a small alphabet	Variable	Words processed per byte	One integer tracks all prefix states	Shift-And
Long pattern	$m=4096$ in multi-megabyte text	Low	Preprocessing and memory	Big-integer bit state grows; linear arrays stay stable	KMP, Z, or runtime
Collision laboratory	Small hash modulus with adversarial collisions	Controlled	Hash hits versus verified matches	Verification preserves exact output	Rabin-Karp
Many texts, one pattern	One pattern searched in 1,000 texts	Variable	Amortized preprocessing	Reusable tables reduce total cost	KMP, Horspool, Shift-And
Unicode code points	ASCII, combining marks, and emoji	Controlled	Semantic agreement and throughput	Agreement requires a fixed symbol-unit contract	Any verified matcher

Cookie Consent