KMP String Matching

The problem

Find every place where a pattern P (length m) occurs inside a text T (length n). Your browser does this with Ctrl + F, editors use it in search-and-replace, and biologists use it to find DNA sequences.

The naive method tries the pattern at every position. After a mismatch it shifts the pattern by one and starts comparing again from the pattern’s first character, re-reading text it has already seen. With text AAAAAAAAAB and pattern AAAAB it does nearly n × m comparisons.

The KMP idea

When a mismatch happens after j characters matched, we already know those j characters: they are P[0…j−1]. Part of them may also be the start of the pattern, and then we don’t need to compare them again.

The LPS table (longest proper prefix that is also a suffix, also called the failure function) stores this for every prefix of the pattern:

lps[8] = 4 because ABAB is both a prefix and a suffix of ABABCABAB.

Searching with the table

Keep two pointers: i in the text and j in the pattern.

• Match: move both right. If j reaches m, a match ends at i, so record it and set j ← lps[m − 1] to keep looking.
• Mismatch with j > 0: set j ← lps[j − 1]. The pattern slides forward by j − lps[j − 1] places, and i stays where it is.
• Mismatch with j = 0: move i one step right.

Because i never moves backwards, the search takes at most about 2n comparisons. On the first example in the 3D model, KMP needs 23 comparisons where the naive method needs 29. The gap grows quickly on repetitive text.

Building the LPS table

The table is built the same way, with the pattern matched against itself. len is the length of the current border:

• If P[i] = P[len]: the border grows, so lps[i] = len + 1.
• Otherwise, if len > 0: fall back to a shorter border with len ← lps[len − 1], and try again.
• Otherwise lps[i] = 0.

This also takes only O(m) time.

Code

def build_lps(p):
    lps = [0] * len(p)
    length, i = 0, 1                    # length of the current border
    while i < len(p):
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]    # try a shorter border
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, p):
    lps, found = build_lps(p), []
    i = j = 0
    while i < len(text):
        if text[i] == p[j]:
            i += 1
            j += 1
            if j == len(p):
                found.append(i - j)
                j = lps[j - 1]          # allow overlapping matches
        elif j:
            j = lps[j - 1]              # slide the pattern, keep i
        else:
            i += 1
    return found

print(build_lps("ABABCABAB"))                      # [0, 0, 1, 2, 0, 1, 2, 3, 4]
print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))   # [10]
print(kmp_search("AABAACAADAABAABA", "AABA"))           # [0, 9, 12]

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> buildLps(const string& p) {
    vector<int> lps(p.size(), 0);
    for (size_t i = 1, len = 0; i < p.size();) {
        if (p[i] == p[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

vector<int> kmpSearch(const string& t, const string& p) {
    vector<int> lps = buildLps(p), found;
    for (size_t i = 0, j = 0; i < t.size();) {
        if (t[i] == p[j]) {
            i++; j++;
            if (j == p.size()) { found.push_back(i - j); j = lps[j - 1]; }
        } else if (j) j = lps[j - 1];
        else i++;
    }
    return found;
}

int main() {
    for (int pos : kmpSearch("AABAACAADAABAABA", "AABA")) cout << pos << " ";   // 0 9 12
}

KMP vs other string-matching algorithms

KMP’s table is really a small automaton: each state is “how much of the pattern has matched”, and that links it to finite automata.

Common mistakes

• Moving i backwards after a mismatch. That throws away the whole point of KMP.
• Using lps[j] instead of lps[j − 1] after a mismatch at position j.
• Forgetting to reset j ← lps[m − 1] after a full match, which misses overlapping matches like AABA in AABAABA.
• Counting the whole string as its own border. The prefix must be proper, shorter than the string.