Python prefix-function search: overlapping matches without rescanning

Operation contract

The importer scans a bounded text field for every occurrence of a nonempty marker, including overlapping occurrences. The prefix array tells it how much matched state remains useful after a mismatch or a complete match. Returning positions in ascending order follows the left-to-right scan; it does not require sorting the result.

Failure and ownership boundary

The program compares code points exactly. It does not normalize text, decode bytes or treat visually equal sequences as equal. Empty markers are rejected rather than implicitly matching every boundary. Use Python’s built-in string operations in ordinary applications unless the all-overlaps or streaming contract justifies a separate implementation. Python Unicode normalization: equality is not visual identity must be decided before matching.

Working program

def marker_positions(text, marker):
    if type(text) is not str or type(marker) is not str or len(text) > 4096 or not 1 <= len(marker) <= 128:
        raise ValueError("text or marker budget")
    prefix = [0] * len(marker)
    matched = 0
    for position in range(1, len(marker)):
        while matched and marker[position] != marker[matched]:
            matched = prefix[matched - 1]
        if marker[position] == marker[matched]:
            matched += 1
        prefix[position] = matched
    found, matched = [], 0
    for position, character in enumerate(text):
        while matched and character != marker[matched]:
            matched = prefix[matched - 1]
        if character == marker[matched]:
            matched += 1
        if matched == len(marker):
            found.append(position - len(marker) + 1)
            matched = prefix[matched - 1]
    return found

print(marker_positions("R41|R41|R42", "R41"))
print(marker_positions("aaaa", "aa"))

Output

[0, 4]
[0, 1, 2]

Costs and limits

For text length n and marker length m, prefix construction plus scanning takes O(n+m) comparisons. Storage is O(m+k) for the prefix array and k returned matches.

Common Mistakes

• Reset to the stored prefix length after a full match to retain overlapping matches.
• Do not conflate code-point positions with encoded byte offsets.

Connected lessons

Python strings and bytes: reject decoding errors before parsing records, Python Unicode normalization: equality is not visual identity, Python regular expressions: use fullmatch for a complete field contract.

Follow the service contract

Python Z string matching: reuse a known matching interval without losing overlaps.