Engineering, Selection & Production Correctness

Correctness Contracts and Edge Cases

Define what a character, position, and match mean before selecting an algorithm. A byte API can split multibyte encodings; a code-point API still treats combining sequences as multiple positions; a grapheme API depends on a documented Unicode segmentation version. Normalization is separate: canonically equivalent NFC and NFD strings compare unequal unless the contract normalizes them.

Specify empty-pattern behavior, overlap policy, duplicate-pattern identity, and interval convention. A mathematical API may report an empty pattern at every boundary $0,\dots,n$; overlapping search should report both occurrences of ana in banana. State whether offsets count bytes, code points, or graphemes and whether ranges are half-open.

Malformed encodings require an explicit strict, replacement, or byte-preserving policy. Sentinels must be unique and outside the alphabet; coordinate compression should reserve a distinct integer rank instead of assuming $ is absent. Guard expressions such as $i+m$, table dimensions, and $n(n+1)/2$ against integer overflow. Dynamic and streaming APIs must also define snapshot, chunk-boundary, concurrency, and buffer-ownership behavior. Randomized APIs must state seed policy, collision bounds, verification, and whether answers are Monte Carlo or Las Vegas.

Testing String Algorithms

Unit tests should cover empty inputs, one-symbol inputs, patterns longer than text, all-equal alphabets, no match, both boundaries, overlaps, duplicates, and non-ASCII symbols. Property tests assert universal facts: every reported interval reproduces the pattern, a suffix array is a sorted permutation, an LCP fits both suffixes, and symmetric edit distance is non-negative and symmetric.

Differential testing compares an optimized algorithm with a deliberately simple exact baseline. Fuzzing varies valid and malformed inputs at decoder, parser, and serialization boundaries. Invariant checks inspect internal state, such as KMP failure links pointing to shorter prefixes. Metamorphic tests derive new cases: reversing both strings preserves Levenshtein distance, and a bijective alphabet renaming preserves exact-match positions. Record seeds and minimize every failure into a stable regression test.

from random import Random


def naive_find_all(text: str, pattern: str) -> list[int]:
    if pattern == "":
        return list(range(len(text) + 1))
    return [
        start
        for start in range(len(text) - len(pattern) + 1)
        if text[start:start + len(pattern)] == 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 > 0 and pattern[i] != pattern[border]:
            border = pi[border - 1]
        if pattern[i] == pattern[border]:
            border += 1
        pi[i] = border
    return pi


def kmp_find_all(text: str, pattern: str) -> list[int]:
    """Report overlapping matches; empty pattern occurs at all boundaries."""
    if pattern == "":
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    matched = 0
    result: list[int] = []
    for index, symbol in enumerate(text):
        while matched > 0 and symbol != pattern[matched]:
            matched = pi[matched - 1]
        if symbol == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            result.append(index - len(pattern) + 1)
            matched = pi[matched - 1]
    return result


def edit_distance_matrix(left: str, right: str) -> int:
    rows, columns = len(left) + 1, len(right) + 1
    dp = [[0] * columns for _ in range(rows)]
    for i in range(rows):
        dp[i][0] = i
    for j in range(columns):
        dp[0][j] = j
    for i in range(1, rows):
        for j in range(1, columns):
            dp[i][j] = min(
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + (left[i - 1] != right[j - 1]),
            )
    return dp[-1][-1]


def edit_distance_rolling(left: str, right: str) -> int:
    if len(left) < len(right):
        left, right = right, left
    previous = list(range(len(right) + 1))
    for i, left_symbol in enumerate(left, start=1):
        current = [i]
        for j, right_symbol in enumerate(right, start=1):
            current.append(min(
                previous[j] + 1,
                current[j - 1] + 1,
                previous[j - 1] + (left_symbol != right_symbol),
            ))
        previous = current
    return previous[-1]


def renamed(text: str, mapping: dict[str, str]) -> str:
    return "".join(mapping[symbol] for symbol in text)


def run_differential_tests(trials: int = 5_000, seed: int = 20260916) -> None:
    rng = Random(seed)
    alphabet = ["a", "b", "c", "é", "😀"]
    for text, pattern in [
        ("", ""), ("abc", ""), ("", "a"),
        ("aaaaa", "aa"), ("banana", "ana"), ("😀a😀a", "😀a"),
    ]:
        assert kmp_find_all(text, pattern) == naive_find_all(text, pattern)

    for _ in range(trials):
        text = "".join(rng.choice(alphabet) for _ in range(rng.randrange(13)))
        pattern = "".join(rng.choice(alphabet) for _ in range(rng.randrange(7)))
        expected = naive_find_all(text, pattern)
        actual = kmp_find_all(text, pattern)
        assert actual == expected, (text, pattern, expected, actual)
        for start in actual:
            assert text[start:start + len(pattern)] == pattern

        left = "".join(rng.choice(alphabet) for _ in range(rng.randrange(8)))
        right = "".join(rng.choice(alphabet) for _ in range(rng.randrange(8)))
        reference = edit_distance_matrix(left, right)
        optimized = edit_distance_rolling(left, right)
        assert optimized == reference
        assert optimized == edit_distance_rolling(right, left)
        assert optimized == edit_distance_rolling(left[::-1], right[::-1])
        assert 0 <= optimized <= len(left) + len(right)

        permutation = alphabet[:]
        rng.shuffle(permutation)
        mapping = dict(zip(alphabet, permutation))
        assert kmp_find_all(renamed(text, mapping), renamed(pattern, mapping)) == actual


if __name__ == "__main__":
    run_differential_tests()
    print("all differential and metamorphic tests passed")

Adversarial and Randomized Failure Modes

Hash tables and rolling hashes can degrade when attackers influence collisions. Deterministic bases and small moduli are easier to attack; use randomized parameters, keyed hashes at trust boundaries, and exact verification when false equality is unacceptable. Backtracking regex engines may explore exponentially many paths for nested ambiguous repetitions; prefer automata engines, safe pattern restrictions, or resource limits.

Recursive parsers and tree traversals can exceed call-stack limits on degenerate inputs, so iterative stacks make resources explicit. In C and C++, a signed char can become a negative table index; convert through unsigned char. Integer overflow can corrupt allocations, rolling products, DP dimensions, counts, and endpoints; validate arithmetic before indexing or allocation and use sufficiently wide modular intermediates.

Performance Engineering

Measure input size, alphabet cardinality, match density, pattern reuse, update/query ratio, allocations, cache misses, peak memory, and tail latency. Big-O bounds do not expose copying, object overhead, branch prediction, memory bandwidth, or preprocessing amortization.

Pass ranges or views instead of copying substrings; reuse DP rows and scratch buffers. Flat arrays exploit cache lines better than pointer-heavy structures, while ropes trade locality for edit efficiency. Dense alphabets favor arrays, bitsets, and packing; sparse alphabets favor maps or sorted edges. SIMD and branchless kernels help only after accounting for setup, alignment, tails, and fallback paths.

Parallel blocks need overlap or boundary-state transfer, and memory bandwidth may limit scaling. For data beyond RAM, measure block transfers and compare cold with warm caches; use sequential scans, batching, blocking, compression, and external merges.

Algorithm Selection by Workload

Begin with semantics: bytes, code points, normalized text, graphemes, tokens, or domain symbols. Then identify exact, mismatch, edit, weighted-alignment, wildcard, regular-language, or grammar recognition requirements.

One exact pattern often needs only a scan, KMP, Z, or Boyer–Moore. Many patterns favor Aho–Corasick; prefix queries favor tries. Many queries over static text justify suffix arrays, FM-indexes, or inverted indexes. Small approximate thresholds favor banded DP, Bitap, or Myers; larger scored alignments favor full DP or seed-and-extend.

Editable text favors ropes or balanced trees with maintained hashes. Compressed workloads must decide whether sequential decode, random access, or direct search is required. Include preprocessing amortization, memory, update frequency, result volume, adversarial exposure, and verification cost. A simple exact baseline plus a measured safe accelerator is often the best production design.

flowchart TD
    START["Define text units and correctness contract"]
    MODE{"Exact, approximate, or language?"}
    EXACT{"Pattern/query workload?"}
    APPROX{"Error model and threshold?"}
    LANGUAGE{"Regular features only?"}
    DYNAMIC{"Static or editable corpus?"}
    SINGLE["Few exact queries: scan, KMP, Z, Boyer-Moore"]
    MULTI["Many patterns: Aho-Corasick or trie"]
    SMALLK["Small k: banded DP, Bitap, Myers"]
    ALIGN["General scoring: alignment DP or seed-and-extend"]
    REGEX["DFA/NFA or safe regex engine"]
    PARSER["CFG parser or specialized nonregular engine"]
    EDITABLE["Rope or balanced tree with hashes"]
    STATIC["Suffix array, FM-index, or inverted index"]
    START --> MODE
    MODE -->|exact| EXACT
    MODE -->|approximate| APPROX
    MODE -->|recognition| LANGUAGE
    EXACT -->|one pattern, few queries| SINGLE
    EXACT -->|many patterns| MULTI
    EXACT -->|many corpus queries| DYNAMIC
    APPROX -->|small bound| SMALLK
    APPROX -->|weighted or large distance| ALIGN
    LANGUAGE -->|yes| REGEX
    LANGUAGE -->|no| PARSER
    DYNAMIC -->|editable| EDITABLE
    DYNAMIC -->|static| STATIC