Knuth-Morris-Pratt (KMP)

Search for a pattern without ever moving backwards in the text. When a mismatch happens, a small table of the pattern's own repeats says how far the pattern can safely slide.

Time	Extra space	Output
\(O(n + m)\), worst case	\(O(m)\) for the table	every position where the pattern starts

The idea

Searching for ABABCABAB, suppose the first four letters ABAB matched and then the fifth failed. The naive method shifts the pattern by one and starts again from scratch, re-reading text it has already seen.

KMP notices that the matched part ABAB ends with AB, which is also how the pattern starts. So after the mismatch, slide the pattern so that its first AB sits under the text's last AB, and carry on comparing from there. No text letter is read twice in a row of successes, and the text pointer never goes back.

How far to slide depends only on the pattern, so it is worked out once, in the prefix function:

\[\pi[i] = \text{length of the longest proper prefix of } P[0..i] \text{ that is also a suffix of it.}\]

For ABABCABAB: \(\pi = [0, 0, 1, 2, 0, 1, 2, 3, 4]\).

How it works

1. Build \(\pi\). Keep k, the length of the current border. For each new letter P[i]: while k > 0 and P[i] ≠ P[k], fall back to k = π[k-1]. If P[i] = P[k], increase k. Set π[i] = k.
2. Search. The same loop on the text: k is how many pattern letters currently match. On a mismatch fall back with \(\pi\); on a match increase k; when k = m, report a match at i - m + 1 and set k = π[m-1] to keep looking for overlapping matches.

Code

PythonJavaC++

def prefix_function(p):
    """pi[i] = the length of the longest proper prefix of p[:i+1] that is also a suffix of it."""
    pi = [0] * len(p)
    k = 0                                    # the length of the current matching prefix
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:        # mismatch: fall back to the next shorter border
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi


def kmp_search(text, p):
    """Every position where p starts in text (Knuth-Morris-Pratt), in O(len(text) + len(p))."""
    if not p:
        return list(range(len(text) + 1))
    pi = prefix_function(p)
    found, k = [], 0                         # k = how many letters of p match right now
    for i, ch in enumerate(text):
        while k > 0 and ch != p[k]:          # never move back in text: shift p using pi instead
            k = pi[k - 1]
        if ch == p[k]:
            k += 1
        if k == len(p):                      # a full match ends at i
            found.append(i - len(p) + 1)
            k = pi[k - 1]                    # keep going, to find overlapping matches too
    return found


if __name__ == "__main__":
    print(prefix_function("ABABCABAB"))
    print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
    print(kmp_search("AAAAA", "AA"), kmp_search("olympus mons", "mars"))

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Kmp {
    /** pi[i] = the length of the longest proper prefix of p[0..i] that is also a suffix of it. */
    static int[] prefixFunction(String p) {
        int[] pi = new int[p.length()];
        int k = 0;                                    // the length of the current matching prefix
        for (int i = 1; i < p.length(); i++) {
            while (k > 0 && p.charAt(i) != p.charAt(k)) k = pi[k - 1];   // fall back to the next shorter border
            if (p.charAt(i) == p.charAt(k)) k++;
            pi[i] = k;
        }
        return pi;
    }

    /** Every position where p starts in text (Knuth-Morris-Pratt), in O(len(text) + len(p)). */
    static List<Integer> kmpSearch(String text, String p) {
        List<Integer> found = new ArrayList<>();
        if (p.isEmpty()) { for (int i = 0; i <= text.length(); i++) found.add(i); return found; }
        int[] pi = prefixFunction(p);
        int k = 0;                                    // how many letters of p match right now
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            while (k > 0 && ch != p.charAt(k)) k = pi[k - 1];   // never move back in text: shift p using pi
            if (ch == p.charAt(k)) k++;
            if (k == p.length()) {                    // a full match ends at i
                found.add(i - p.length() + 1);
                k = pi[k - 1];                        // keep going, to find overlapping matches too
            }
        }
        return found;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(prefixFunction("ABABCABAB")));
        System.out.println(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));
        System.out.println(kmpSearch("AAAAA", "AA") + " " + kmpSearch("olympus mons", "mars"));
    }
}

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

// pi[i] = the length of the longest proper prefix of p[0..i] that is also a suffix of it.
vector<int> prefixFunction(const string& p) {
    vector<int> pi(p.size(), 0);
    int k = 0;                                       // the length of the current matching prefix
    for (size_t i = 1; i < p.size(); i++) {
        while (k > 0 && p[i] != p[k]) k = pi[k - 1];   // mismatch: fall back to the next shorter border
        if (p[i] == p[k]) k++;
        pi[i] = k;
    }
    return pi;
}

// Every position where p starts in text (Knuth-Morris-Pratt), in O(len(text) + len(p)).
vector<int> kmpSearch(const string& text, const string& p) {
    vector<int> found;
    if (p.empty()) { for (size_t i = 0; i <= text.size(); i++) found.push_back(i); return found; }
    vector<int> pi = prefixFunction(p);
    int k = 0, m = p.size();                         // k = how many letters of p match right now
    for (int i = 0; i < (int)text.size(); i++) {
        while (k > 0 && text[i] != p[k]) k = pi[k - 1];   // never move back in text: shift p using pi
        if (text[i] == p[k]) k++;
        if (k == m) {                                // a full match ends at i
            found.push_back(i - m + 1);
            k = pi[k - 1];                           // keep going, to find overlapping matches too
        }
    }
    return found;
}

string show(const vector<int>& v) {
    string s = "[";
    for (size_t i = 0; i < v.size(); i++) s += (i ? ", " : "") + to_string(v[i]);
    return s + "]";
}

int main() {
    cout << show(prefixFunction("ABABCABAB")) << "\n";
    cout << show(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB")) << "\n";
    cout << show(kmpSearch("AAAAA", "AA")) << " " << show(kmpSearch("olympus mons", "mars")) << "\n";
}

Output: the prefix function [0, 0, 1, 2, 0, 1, 2, 3, 4]; a match at [10]; then [0, 1, 2, 3] (overlapping matches of AA in AAAAA) and [] (mars does not appear in olympus mons).

When to use it

• Searching a stream (a file read once, network packets): the text pointer never goes back, so nothing needs to be buffered.
• Guaranteed time: no bad cases, unlike the naive method or hashing.
• The prefix function on its own answers other questions: the shortest period of a string is \(m - \pi[m-1]\); counting how often each prefix occurs; building an automaton for the pattern.

Common mistakes

• Moving the text pointer back after a mismatch: that is the naive method again.
• Using if instead of while when falling back: one step back may not be enough.
• Forgetting k = π[m-1] after a match: the next search step would read past the end of the pattern, or miss overlapping matches.
• Off-by-one in \(\pi\): it uses proper prefixes, so \(\pi[0] = 0\) always.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: ABABCABAB in ABABDABACDABABCABAB

Text position	What happens	k after
0–3	A B A B match	4
4	D ≠ C: fall back to π[3] = 2; D ≠ A: fall back to π[1] = 0; D ≠ A	0
5–7	A B A match	3
8	C ≠ B: fall back to π[2] = 1; C ≠ B: to π[0] = 0; C ≠ A	0
9	D ≠ A	0
10–18	all nine letters match	9 → match at 10

23 letter comparisons in all, against up to \(11 \times 9 = 99\) for the naive method on this text.

Building π for ABABCABAB: B vs A no (0); A = A (1); B = B (2); C vs A after falling back from 2 → 0: no (0); then A B A B grow it again to 1, 2, 3, 4.

The math: why the fall-back is safe, and the linear bound

Borders of borders. If \(b\) is the longest border of \(s\), then the borders of \(s\) are exactly \(b\) and the borders of \(b\). So the borders of \(P[0..i]\), from longest to shortest, are \(\pi[i], \pi[\pi[i]-1], \dots\), down to 0. Falling back with \(k \leftarrow \pi[k-1]\) visits them in that order.

Nothing is skipped. After a mismatch with \(k\) letters matched, any match of \(P\) that starts inside those \(k\) letters must line up a prefix of \(P\) with a suffix of the matched part, which is a border. Trying the borders from longest to shortest therefore never jumps over a possible match.

Linear time (amortized). In the search, \(k\) goes up by at most 1 per text letter, so at most \(n\) times in total. Each fall-back makes \(k\) strictly smaller, and \(k \ge 0\), so there are at most \(n\) fall-backs. Total comparisons: at most \(2n\). The same argument gives \(2m\) for building \(\pi\).

Period. \(P\) has period \(p\) exactly when it has a border of length \(m - p\), so its shortest period is \(m - \pi[m-1]\).

Watch it step by step

Green letters are already matched, orange is the pair being compared, red a mismatch. Notice how the pattern jumps forward but the text column never moves left.

Variations and related ideas

• KMP automaton: precompute, for every state \(k\) and letter \(c\), the next state; then the search is one table look-up per letter.
• Aho–Corasick: KMP for many patterns at once, on a trie with failure links; used in virus scanners and grep -F.
• Boyer–Moore: compares from the end of the pattern and can skip large parts of the text; often faster in practice on natural language.
• The Z-algorithm computes closely related information and can replace \(\pi\) in most uses.

See also

• Rabin-Karp
• Z-algorithm
• Trie

References

• D. E. Knuth, J. H. Morris and V. R. Pratt, "Fast pattern matching in strings", SIAM Journal on Computing 6(2), 1977.
• T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 32 (string matching).
• D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.