KMP, prefix functions and the Z algorithm

Naive pattern search may repeat many comparisons after mismatches. KMP uses pi[i], the longest proper prefix of pattern[0:i+1] that is also its suffix. On mismatch set j=pi[j−1] without moving the text index backward.

Pattern aba has pi=[0,0,1]. After a complete match, falling back via pi finds overlaps. Z[i] measures the prefix match starting ati; a maintained match box enables linear construction. Pattern+separator+text methods need a genuinely distinct separator.

Algorithms match supplied symbols, not linguistic meaning. Unicode normalisation, empty patterns and byte versus code-point offsets need explicit contracts.

def kmp(text, pattern):
    if not pattern: return list(range(len(text)+1))
    pi=[0]*len(pattern); j=0
    for i in range(1,len(pattern)):
        while j and pattern[i] != pattern[j]: j=pi[j-1]
        if pattern[i] == pattern[j]: j+=1
        pi[i]=j
    out=[]; j=0
    for i,c in enumerate(text):
        while j and c != pattern[j]: j=pi[j-1]
        if c == pattern[j]: j+=1
        if j == len(pattern): out.append(i-j+1); j=pi[j-1]
    return out
assert kmp("ababa","aba") == [0,2]