Build the KMP Table

The Idea

The table holds one number per position: the length of the longest proper prefix of the pattern that is also a suffix ending there. That is the border. Build it by matching the pattern against itself with a carried border length k. On a mismatch, fall back to the border of that border — table[k - 1] — instead of restarting. Later, a search that breaks at position i reads the table and resumes without re-reading the text.

Real-World Example

A log watcher scanning a stream for the marker --END--. When the stream breaks the match four characters in, the table says how much of the marker is still alive in what was just read, so the watcher never rewinds the stream.

The Code

def failure_table(p):
    table = [0] * len(p)
    k = 0                            # length of the current border
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = table[k - 1]         # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        table[i] = k
    return table

print(failure_table("ababaca"))   # [0, 0, 1, 2, 3, 0, 1]

print(failure_table("aabaa"))