KMP:Find a Pattern Without Sliding Back on the Text

A log scraper looks for the SKU prefix ABABC in every warehouse line. The intern writes the nested scan: for each start i, compare pattern[0…] until a miss, then i++. A million-character dump with a pattern that almost matches at every offset re-reads the same text characters. The job is “find this needle,” not “restart the needle on every haystack index.”

KMP precomputes, for each pattern prefix, the longest proper prefix that is also a suffix — then a mismatch jumps the pattern, never the text. You pay O(m) to build that table once. The scan is O(n). Worst case stays linear. Naive backtracking on the text is not.

This post is that table and that scan. Families and the catalog live on the Algorithms Roadmap. Rolling hashes for many patterns are Rabin-Karp. Skipping from a late mismatch is Boyer-Moore. Many needles in one pass is Aho-Corasick. None of those re-teach LPS.

The nested scan that slides back

The honest nested loop is easy to prove: every alignment is tried.

static int indexOfNaive(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    outer:
    for (int i = 0; i + m <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                continue outer;
            }
        }
        return i;
    }
    return -1;
}

On text = "ABABABC" and pattern = "ABABC", the first alignment matches ABAB then fails on C vs A. Naive then starts over at i = 1. The text index went back. That is the bill KMP refuses.

Re-reading a character you already matched is the naive tax. If the pattern has self-overlap, you already know a shorter prefix is sitting on the text. The LPS table is that knowledge, written down.

String.indexOf in the JDK is not a promise of KMP. Hot paths in StringLatin1 / StringUTF16 use specialized scans. This post is the procedure you write when the needle is a char[] you own, or when the interview asks what “linear string match” actually means.

The LPS table: longest proper prefix that is a suffix

lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of that same prefix. Proper: not the whole prefix. lps[0] is 0.

pattern = A B A B C
index     0 1 2 3 4
lps       0 0 1 2 0

ABAB: longest proper prefix that is a suffix is AB (length 2). ABABC: nothing proper works, so 0.

Build it the same way you will scan: two indexes, never retreat the “text” of the pattern except by lps.

static int[] lps(char[] p) {
    int m = p.length;
    int[] lps = new int[m];
    int len = 0;
    int i = 1;
    while (i < m) {
        if (p[i] == p[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

len is the candidate prefix length. A match grows it. A mismatch jumps len to lps[len - 1] — the next-best prefix you already computed. That jump is why the builder is O(m), not quadratic.

Note: LPS is sometimes called π, the failure function, or the prefix table. Same array. Do not store “the next character to try” as a separate automaton unless you are already in Aho-Corasick.

The scan: text index only advances

i walks the text. j walks the pattern. A match grows j. A mismatch, if j > 0, sets j = lps[j - 1] and does not decrement i.

static int indexOfKmp(String text, String pattern) {
    if (pattern.isEmpty()) {
        return 0;
    }
    char[] t = text.toCharArray();
    char[] p = pattern.toCharArray();
    int[] lps = lps(p);
    int i = 0;
    int j = 0;
    while (i < t.length) {
        if (t[i] == p[j]) {
            i++;
            j++;
            if (j == p.length) {
                return i - j;
            }
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return -1;
}

Walk ABABABC vs ABABC:

i  t[i]  j  action
0  A     0  match → j=1
1  B     1  match → j=2
2  A     2  match → j=3
3  B     3  match → j=4
4  A     4  mismatch (want C); j = lps[3] = 2
4  A     2  match → j=3   (i did not go back)
5  B     3  match → j=4
6  C     4  match → j=5   found at i-j = 2

Index 4 was compared twice against the pattern, never rewound in the text. The overlap AB was already sitting there; LPS said so.

Empty pattern: return 0 (Java String.indexOf does). Empty text, non-empty pattern: -1. First occurrence only: return on j == m. All occurrences: after a hit, set j = lps[j - 1] and keep scanning — the same jump that handles overlap (AAA in AAAA).

Complexity and the JDK

What	Cost	Why
Build LPS	O(m)	Each i advances at most m times; len drops but never below 0 in a way that re-scans
Scan	O(n)	i only increases, or j drops via LPS without moving i backward
Extra space	O(m)	The lps array
Naive worst case	O(n · m)	Almost-match at every alignment

Linear in the text, linear in the pattern, no retreat on the haystack. String.contains / indexOf remain the default in application code. Write KMP when you own the buffers, when you need every overlapping hit, or when the interview is the LPS table.

When not to use KMP

• One short needle in a short haystack. The nested scan is clearer. Constant factors on tiny n win.
• Many different needles. KMP once per pattern still scans the text once per needle. Aho-Corasick builds one automaton.
• You can skip from the end of the window. English-like alphabets with a mismatch near the end of the pattern often want Boyer-Moore.
• You needed a hash fingerprint, not an exact automaton. Rabin-Karp compares rolling hashes first.
• Regex / Unicode grapheme clusters. KMP is code-unit equality. Graphemes, case-folding, and Pattern are a different job.

Cheat sheet

Job:       first (or every) exact occurrence of pattern in text
LPS[i]:    longest proper prefix that is also a suffix of p[0..i]
Build:     two indexes on the pattern; mismatch → lps[len-1]
Scan:      i never decreases; mismatch → j = lps[j-1]
Time:      O(n + m)   Extra: O(m)
JDK:       String.indexOf is not "call KMP"; write the loop when you own it
Not this:  many needles, skip-from-end, rolling hash, regex

Do:

• Build LPS once; reuse it for every scan of that needle.
• After a hit, set j = lps[j - 1] if you still need overlapping matches.
• Treat empty pattern as a hit at 0.

Don’t:

• Decrement the text index on a mismatch.
• Store lps[i] = i (the whole prefix is not proper).
• Quote KMP for a dictionary of thousands of patterns.

Wrap-up

KMP replaces “slide the needle and reread the haystack” with a prefix table: the longest proper prefix that is already a suffix tells you how far the pattern can jump. The text index only moves forward. Linear time is the contract, not a typical-case hope.

The layout was already a char[]. The procedure is LPS plus that scan. When the job is many needles, a skip table, or a rolling hash, pick the next string post — starting with Rabin-Karp when the fingerprint is the primitive.

Next optional step in the series Rolling hash when you need many pattern checks, not one LPS table. Rabin-Karp: Rolling Hash When You Need Many Pattern Checks →