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

Operation contract

The matcher combines the pattern, one unique object sentinel and the text into an owned symbol list. The sentinel cannot collide with an arbitrary character, unlike a guessed delimiter such as a dollar sign. A half-open matching interval lets positions inside a known match reuse a lower bound before extending it. Positions with a Z value at least the pattern length identify text matches, including overlapping matches.

Failure and ownership boundary

The input contract accepts strings up to 128 code points for the text and 32 for the pattern. An empty pattern matches every boundary, including the final boundary. Indices count code points, not encoded bytes or grapheme clusters. Python prefix-function search: overlapping matches without rescanning, Python strings and bytes: reject decoding errors before parsing records and Python Unicode normalization: equality is not visual identity must use compatible index rules.

Working program

def z_matches(text, pattern):
    if type(text) is not str or type(pattern) is not str or len(text) > 128 or len(pattern) > 32:
        raise ValueError("bounded strings required")
    if not pattern:
        return list(range(len(text) + 1))
    symbols = list(pattern) + [object()] + list(text)
    matched = [0] * len(symbols)
    left = right = 0
    for position in range(1, len(symbols)):
        if position < right:
            matched[position] = min(right - position, matched[position - left])
        while position + matched[position] < len(symbols) and symbols[matched[position]] == symbols[position + matched[position]]:
            matched[position] += 1
        if position + matched[position] > right:
            left, right = position, position + matched[position]
    offset = len(pattern) + 1
    return [position - offset for position in range(offset, len(symbols)) if matched[position] >= len(pattern)]

print("overlaps:", z_matches("ababa", "aba"))
print("delimiter text:", z_matches("$a$a", "$a"))
print("empty:", z_matches("ab", ""))

Output

overlaps: [0, 2]
delimiter text: [0, 2]
empty: [0, 1, 2]

Costs and limits

For text length n and pattern length m, interval reuse bounds extension work to O(n + m), with O(n + m) owned storage and returned-match space. This eager matcher is not a streamed matcher for arbitrarily large input.

Common Mistakes

• A guessed text delimiter may occur in the received text.
• Specify what an empty pattern means instead of leaving it accidental.

Connected lessons

Python prefix-function search: overlapping matches without rescanning, Python longest palindrome: expand around odd and even centers, Python strings and bytes: reject decoding errors before parsing records.