KMP

KMP, named after Knuth, Morris and Pratt (1977), finds every place of a pattern in O(n + m) time and never reads a letter of the text twice. All it needs is one table about the pattern: for each start of the pattern, the length of its longest border.

Borders

A border of a string is a piece that is both a start of it and an end of it, but not the whole string. The empty string (length 0) is a border of every string.

• "abacaba" has the borders "a" and "aba" (and the empty one).
• "aaaa" has "a", "aa" and "aaa": borders can overlap.
• "abc" has only the empty border.

Why borders matter for searching: suppose P has matched j letters at some place, then the next letter differs.

Here is why. The matched part of the text is exactly P[0..j−1]. If P occurred at a place s letters further right, with 0 < s < j, then the last j − s letters of the matched part would equal the first j − s letters of P. That makes them a border of P[0..j−1] of length j − s. So the only places worth trying are those where a border lines up, and the longest border gives the smallest slide.

The border table π

For a pattern P with m letters, the border table (also called the prefix function or failure function) is π[i] = the length of the longest border of P[0..i], the first i + 1 letters (π is the Greek letter pi). For "abacabab":

P   a  b  a  c  a  b  a  b
π   0  0  1  0  1  2  3  2
# π[6] = 3: "abacaba" starts and ends with "aba"
# π[7] = 2: "abacabab" starts and ends with "ab"

Two facts about borders make the table enough for everything.

• A border of a border is a border. If b is a start and an end of s, and c is a start and an end of b, then c is a start and an end of s.
• Every shorter border is a border of the longest one. Two borders of s are both starts of s, so the shorter is a start of the longer; both are ends of s, so the shorter is also an end of the longer.

So the borders of P[0..i], from longest to shortest, have lengths π[i], then π[π[i] − 1], then the same step again, down to 0. The table lists every border, not only the longest.

Building π in O(m)

A border of P[0..i] of length L > 0 is a border of P[0..i−1] of length L − 1, followed by the letter P[i], which must equal P[L − 1]. So try the borders of P[0..i−1] from the longest down, and take the first one that the letter P[i] can extend:

def border_table(p):
    m = len(p)
    pi = [0] * m
    k = 0                        # length of the border being grown
    for i in range(1, m):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]        # the next shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

Step through the first variant. The copy of P under P shows the border being tried: its letter k sits under letter i.

Cost. The inner while loop can run many times for one i, so the count needs care. k starts at 0, grows by at most 1 for each i, and every turn of the while loop makes it smaller, but never below 0. So over the whole run the loop turns at most m times: it cannot take away more than was added. Together with one comparison per i, that is at most 2m comparisons. This style of counting, where a cost is paid for by earlier cheap steps, is called an amortised count (BIGO-7).

Searching without stepping back

The search runs the same loop over the text. j is the number of letters of P matched so far. A mismatch slides P by the slide rule: j = pi[j - 1]. The place i in the text only moves forward.

# one letter ch = t[i] of the text, with j letters of P matched
while j > 0 and ch != p[j]:
    j = pi[j - 1]              # slide P; i stays
if ch == p[j]:
    j += 1                     # one more letter matched

Step through the second variant. At the mismatch, five letters "ababa" had matched, and π[4] = 3: its last three letters "aba" are also P’s first three. P slides right by 2 and those three letters stay matched, so nothing is compared twice.

Why nothing is missed. By the slide rule, no place between the old and the new place of P can hold P. When j reaches m, P ends at place i, so it starts at i − m + 1; then j = pi[m - 1] applies the same rule, so overlapping occurrences are found too. Putting the table and this step together is STRG-P2.

Cost. Each comparison either matches (and i moves right) or fails (and P slides right, or i moves right when j is 0). i moves at most n times, and the start of P, i - j, also only moves right, at most n times. So the search makes at most 2n comparisons, and with the table, KMP costs O(n + m) time and O(m) extra memory. It reads the text once from left to right, so it also works on a text that arrives a piece at a time, such as a stream from the network.

More from the table

• The shortest period. The smallest p > 0 with s[i] = s[i + p] for every valid i is m − π[m − 1]. A string is a whole number of copies of a shorter block (like "abcabcabc") exactly when this period is less than m and divides m.
• How often each start of P occurs in P. Every border chain from each π[i] adds one occurrence; adding them up for all i takes O(m).
• An automaton. For a small alphabet, the table can be turned into a full “next state” table, so each text letter costs exactly one lookup.
• Many patterns at once. The Aho–Corasick method builds a trie of all the patterns (TRIE-1) and adds border links between its nodes, the same idea as π. It finds every place of every pattern in one pass over the text.

In Python, KMP over a million letters takes about half a second, while t.find(p) runs in C and is far faster for one search. KMP wins when there are many overlapping occurrences, when the text is a stream, and when you need the table itself.

Now try STRG-P2, Every place, fast.