Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 17

Prefix functions and overlapping string matches

Reuse proven pattern borders rather than rescanning text and preserve overlapping matches with explicit Unicode semantics.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Define what a character and a match mean
A prefix value records the longest proper border
Track the matched pattern prefix while streaming text

Define what a character and a match mean

This lesson searches exact Python strings by Unicode code points, not user-perceived grapheme clusters or locale-insensitive equivalence. Visually similar strings can have different code-point sequences. If normalization or case folding is required, define it before matching and explain how transformed positions map back to original text. A match result contains starting indices, including overlaps. An empty pattern is defined here to match every boundary from0 through len(text). These are deliberate API choices, not universal conventions. The algorithm assumes constant-time equality for individual sequence elements under its simplified analysis.

A prefix value records the longest proper border

For a pattern prefix ending at index i, pi[i] is the length of the longest proper prefix that is also a suffix. Proper excludes the entire current prefix. The first program extends the previous border when the next characters agree. On mismatch, it falls back to the border of that border, pi[j-1], because shorter candidates not on this chain cannot preserve the already matched suffix. Setting j to j-1 blindly loses that structural information and can add unnecessary work. The resulting table summarizes reusable equality facts inside the pattern before text is examined.

python Self-contained Python3 algorithm example using synthetic local data.

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

print(prefix_function("ababaca"))
print(prefix_function(""))

Expected output

[0, 0, 1, 2, 3, 0, 1]
[]

At the final a, border length1 is valid. At c, earlier a/b border candidates all fail and the border becomes0.

Track the matched pattern prefix while streaming text

The second program maintains j as the length of the pattern prefix equal to a suffix of text processed so far. Mismatches follow the prefix table without moving the text index backward. On a full match, it records the start and falls back to pi[j-1], preserving a border that can participate in an overlapping next match. Resetting j to zero after every match would miss overlaps such as aa in aaaa. The implementation does not join pattern and text with a separator, avoiding a separate requirement to choose a symbol absent from both inputs.

python Self-contained Python3 algorithm example using synthetic local data.

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

def find_all(text, pattern):
    if not pattern:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    matches, j = [], 0
    for i, char in enumerate(text):
        while j and char != pattern[j]:
            j = pi[j - 1]
        if char == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = pi[j - 1]
    return matches

print(find_all("aaaa", "aa"))
print(find_all("باباب", "باب"))
print(find_all("ab", ""))

Expected output

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

The Arabic fixture uses exact unvowelled code points and includes overlapping matches. Empty-pattern output lists boundaries, not characters.

Nested fallback loops still have a linear total bound

In prefix construction, j increases by at most one per outer step and each fallback strictly decreases it. Across the run, total decreases are bounded by previous increases, giving linear table work. The same potential-style reasoning applies to text scanning: successful extensions increase j, while failures consume that accumulated progress without revisiting text positions. With pattern length m, text length n, and z output matches, the total is O(m+n+z), using O(m+z) stored space in this materializing API. Merely seeing a while inside a for is insufficient to conclude quadratic complexity.

Preprocessing is reusable only for the same pattern contract

If many texts share one fixed pattern, its prefix table can be retained and reused. A changed pattern, normalization rule, or comparison policy invalidates that table. A streaming matcher can also retain j between chunks, but match indices need a running global offset and the same character-decoding boundary across chunks. Splitting raw bytes in the middle of a Unicode encoding is a separate decoding problem, not something a string matcher solves. Do not convert code-point indices directly into byte offsets or grapheme positions without the necessary mapping. Keep those representation contracts explicit.

Compare every small result with direct slicing

For tiny strings over a small alphabet, enumerate texts and patterns and compare find_all with checking every valid starting position by slicing. Include repeated symbols, no match, pattern longer than text, empty text, empty pattern, and overlapping matches. Test a few explicit Unicode fixtures separately from ASCII enumeration. Verify the prefix table directly by examining every proper border for small patterns. These independent references may be slower but are transparent. The finite suite supports the border proof; it does not establish grapheme-aware matching, locale collation, or large-text performance claims.

Common errors and fixes

Overlapping matches disappear

Why it happens: The matched-prefix length was reset to zero after success.
How to fix it: Fall back to the full match’s longest proper border.
Prevent it next time: Test aa in aaaa and repeated Arabic patterns.

A changed pattern reuses an old prefix table

Why it happens: Cache identity omitted the pattern or comparison policy.
How to fix it: Rebuild when any preprocessing dependency changes.
Prevent it next time: Change a pattern while preserving its length.

Code-point indices are reported as byte offsets

Why it happens: String and encoded-byte representations were conflated.
How to fix it: Keep offsets in the declared representation or build an explicit mapping.
Prevent it next time: Include multibyte and combining-character fixtures.

Check your understanding

1. Why does aa in aaaa have three results?

Show worked solution

The starts0,1,2 each select two consecutive a characters. Overlap is allowed by the contract, so finding the first occurrence cannot discard the shared suffix. Falling back to border length1 after each full match retains the next possible overlap.

2. Why can the nested fallback loops remain linear?