Lesson 7 · Core algorithms

Knuth–Morris–Pratt (KMP) Algorithm

KMP turns information inside the pattern into a failure table. On a mismatch it preserves the longest suffix that is also a pattern prefix, avoiding comparisons the text has already proved.

What Naive Matching Throws Away

The obvious way to find a pattern of length m in a text of length n is to try every starting position: align the pattern at index 0, compare characters until a mismatch, then slide to index 1 and start over. That is O(n · m) in the worst case.

The waste is specific and worth seeing concretely. Suppose the pattern is ABABC and the first four characters have matched before the fifth fails. The naive algorithm slides the pattern one position and re-compares from scratch — but it already knows what those four text characters were. They were ABAB, because they matched.

That knowledge is enough to skip work. Since AB is both a prefix and a suffix of the matched portion ABAB, the pattern can be shifted two positions instead of one, and the first two characters are known to match already. Comparisons for positions 1 and 2 need never happen.

Knuth–Morris–Pratt turns that observation into an algorithm. It precomputes, for every prefix of the pattern, how far the pattern may safely jump on a mismatch there — and the crucial consequence is that the text pointer never moves backwards.

That single property gives the bound. The text index advances at most n times and never retreats, and the pattern index changes are bounded by the same total, so matching is O(n). Building the table is O(m), giving O(n + m) overall — linear in the combined input, against the naive O(n·m).

Naive matching re-compares text it has already matched
A matched prefix that is also a suffix permits a longer shift
KMP precomputes those shifts so the text pointer never retreats
O(n + m) total against the naive O(n · m)

The LPS Table

The precomputed table is the LPS array — longest proper prefix which is also a suffix. LPS[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].

Proper matters: the whole string does not count as its own prefix here, or every entry would trivially be i+1 and the table would carry no information.

For the pattern ABABCABAB, the table is [0, 0, 1, 2, 0, 1, 2, 3, 4]. Reading a few entries makes it concrete. At index 3 the prefix is ABAB, whose longest proper prefix that is also a suffix is AB, of length 2. At index 4 the prefix is ABABC; the trailing C appears nowhere in the pattern's prefixes, so the value drops to 0. At index 8 the prefix is ABABCABAB and the shared prefix-suffix is ABAB, of length 4.

The table is built by matching the pattern against itself, using the same jump logic the search will use. Keep two indices: i scanning forward from 1, and len holding the length of the current match. If pattern[i] == pattern[len], increment both and record LPS[i] = len. If they differ and len is non-zero, do not reset it to zero — set len = LPS[len - 1] and retry the comparison without advancing i. Only when len is already zero is LPS[i] set to 0 and i advanced.

That fallback line is the one people get wrong, and it is the same recursion the search uses: a failed extension does not discard everything, it falls back to the next-best shorter overlap.

Construction is O(m) by the same argument as the search: len increases at most m times in total and each decrease is bounded by the increases, so the retry loop cannot do more than O(m) work overall.

LPS for the pattern ABABCABAB
i	Prefix	Longest proper prefix = suffix	LPS[i]
0	A	—	0
1	AB	—	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABC	—	0
7	ABABCABA	ABA	3
8	ABABCABAB	ABAB	4

LPS[i] is the longest proper prefix that is also a suffix at i
Proper excludes the whole string, or the table says nothing
Built by matching the pattern against itself with the same fallback
On mismatch during construction, len = LPS[len−1] — never reset to 0

Searching with the Failure Function

With the table built, the search keeps two indices: i into the text and j into the pattern, both starting at 0.

On a match — text[i] == pattern[j] — advance both. If j reaches m, a full occurrence has been found at position i − m; to continue searching for further occurrences, set j = LPS[m - 1] rather than 0, which allows overlapping matches to be found.

On a mismatch, the behaviour depends on j. If j is non-zero, set j = LPS[j - 1] and do not advance i — the pattern slides forward while the text pointer stays put, because the prefix of length LPS[j-1] is already known to match. If j is zero, there is nothing to fall back on, so advance i.

The invariant to state is that pattern[0..j-1] always matches the j text characters ending just before i. Every branch preserves it: matching extends it by one, and the fallback shortens it to the longest overlap that still holds.

The reason this is linear is that i never decreases. It advances on every match and on every zero-j mismatch, so it moves at most n times. Meanwhile j increases only when i does, and each fallback strictly decreases it — so the total number of fallbacks across the whole run is bounded by the total increases, which is n. Amortised, the work is O(n).

That amortised argument is what an exam answer needs. The inner fallback loop looks as though it could be O(m) per character, and showing why it is not is the substance of the analysis.

On mismatch with j > 0: j = LPS[j−1], and i stays where it is
On mismatch with j == 0: advance i
After a full match, j = LPS[m−1] to allow overlapping occurrences
i never decreases, so the whole search is amortised O(n)

Implementation

Build LPS, then match without rewinding

def lps(pattern):
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        table[i] = j
    return table

def find(text, pattern):
    table = lps(pattern)
    j = 0
    for i, c in enumerate(text):
        while j and c != pattern[j]:
            j = table[j - 1]
        if c == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1

print("Match index:", find("ABABAC", "ABAC"))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
    string t="ABABAC",p="ABAC";
    vector<int>a(p.size());
    for(int i=1,j=0;i<p.size();i++)
    {
        while(j&&p[i]!=p[j])j=a[j-1];
        if(p[i]==p[j])j++;
        a[i]=j;
    }
    for(int i=0,j=0;i<t.size();i++)
    {
        while(j&&t[i]!=p[j])j=a[j-1];
        if(t[i]==p[j])j++;
        if(j==p.size())
        {
            cout<<"Match index: "<<i-j+1;
            break;
        }
    }
}

class Main
{
    public static void main(String[]z)
    {
        String t="ABABAC",p="ABAC";
        int[]a=new int[p.length()];
        for(int i=1,j=0;i<p.length();i++)
        {
            while(j>0&&p.charAt(i)!=p.charAt(j))j=a[j-1];
            if(p.charAt(i)==p.charAt(j))j++;
            a[i]=j;
        }
        for(int i=0,j=0;i<t.length();i++)
        {
            while(j>0&&t.charAt(i)!=p.charAt(j))j=a[j-1];
            if(t.charAt(i)==p.charAt(j))j++;
            if(j==p.length())
            {
                System.out.print("Match index: "+(i-j+1));
                break;
            }
        }
    }
}

Watch it run

Step through it

Running on text ABABAC; pattern ABAC

Output

Read all 14 Steps

Start LPS Allocate [0,0,0,0] for ABAC.
LPS index 1 B differs from A, so LPS[1]=0.
LPS index 2 A matches the prefix A; LPS[2]=1.
LPS index 3 C mismatches B, fall back from length 1 to zero; C also mismatches A.
LPS complete The failure table is [0,0,1,0].
Match text 0 A matches pattern[0].
Match text 1 B extends the match to length two.
Match text 2 A extends it to length three.
Mismatch at text 3 Text B mismatches expected C; do not rewind the text pointer.
Fallback with LPS Set pattern length from 3 to LPS[2]=1.
Reuse text 3 The same text B now matches pattern[1].
Match text 4 A matches pattern[2].
Match text 5 C matches pattern[3].
Pattern complete Four matched characters end at index 5, so the start is 2.

Boundaries, Traps, and Alternatives

An empty pattern should be handled explicitly — most conventions say it matches at position 0. A pattern longer than the text can never match and is worth rejecting up front rather than relying on the loop to fall through.

Overlapping occurrences are the detail most implementations get wrong. Searching for AAA in AAAAA has matches at positions 0, 1 and 2. Resetting j = 0 after a match finds only positions 0 and 2; resetting to LPS[m-1] finds all three. Which is correct depends on the problem, so decide deliberately rather than by default.

LPS[j-1] versus LPS[j] is the classic off-by-one. The fallback uses the entry for the last matched character, which is at index j−1 since j is the count of matched characters. Writing LPS[j] shifts every jump by one and produces a search that mostly works and occasionally misses.

Two properties of the LPS table are worth knowing beyond searching, since they appear as standalone problems. The shortest repeating unit of a string of length m is m - LPS[m-1] when that value divides m evenly — which detects whether a string is a repetition of some substring. And appending a sentinel to one string before concatenating another lets the LPS table compute the longest overlap between them, which is the basis of shortest-palindrome constructions.

Against the alternatives: KMP is O(n + m) guaranteed, with O(m) extra space and no randomisation. Rabin–Karp is O(n + m) expected but O(n·m) worst case, and wins when searching for many patterns at once via a shared hash. Boyer–Moore can skip ahead by up to m characters and is sublinear in practice on large alphabets, which is why it and its variants back most real grep implementations — KMP's advantage is its worst-case guarantee and its simplicity, not raw speed.

For many patterns simultaneously, Aho–Corasick generalises KMP's failure function to a trie of patterns, matching all of them in one pass over the text.

Reset to LPS[m−1] after a match to catch overlapping occurrences
LPS[j−1], not LPS[j] — j counts matched characters
m − LPS[m−1] gives the shortest repeating unit when it divides m
Boyer–Moore is faster in practice; KMP guarantees the worst case