Where the naive scan actually costs you
Trying the pattern at every text position, comparing left to right and abandoning on the first mismatch, is O of n times m in the worst case for a text of length n and a pattern of length m. People underrate this because on ordinary English text it behaves like O of n: the first character usually mismatches, so each attempt costs one comparison.
Name the input where it does not. A text of a thousand a's and the pattern of a hundred a's followed by a b: every starting position matches ninety-nine characters and fails on the hundredth, so every position costs a hundred comparisons and nothing is learned. That is the shape an adversary supplying either the text or the pattern will choose.
What the naive scan wastes is knowledge. Having matched ninety-nine a's, it already knows the next ninety-eight text characters are a's, and it compares them again anyway.
What the table entry means
For each position i in the pattern, the table holds the length of the longest proper prefix of the pattern that is also a suffix of the pattern's prefix ending at i. Proper means shorter than the string itself, otherwise the whole prefix would trivially qualify and every entry would be its own length. Being a prefix of the pattern and simultaneously a suffix of the part matched so far is exactly the condition for it to be reusable as a head start.
Compute it by hand on the pattern ababaca, prefix by prefix. For a there is no proper prefix that is also a suffix, so 0. For ab, no, so 0. For aba, the prefix a is also the suffix, so 1. For abab, ab is both, so 2. For ababa, aba is both, so 3. For ababac, nothing works because the string now ends in c, so 0. For ababaca, a is both, so 1. The table is 0, 0, 1, 2, 3, 0, 1.
Read the fifth entry as the algorithm reads it. If you have matched ababa and the next character disagrees with the pattern's sixth, you do not restart: the last three characters matched are aba, which is also the pattern's first three, so you keep those three and resume comparing from the pattern's fourth. The text index has not moved.
Building the table with itself
The table is computed by matching the pattern against its own prefixes with the same fallback rule, which is why the builder looks almost identical to the search.
int[] prefixFunction(String p) {
int[] table = new int[p.length()];
int length = 0;
for (int i = 1; i < p.length(); i++) {
while (length > 0 && p.charAt(i) != p.charAt(length)) {
length = table[length - 1];
}
if (p.charAt(i) == p.charAt(length)) length++;
table[i] = length;
}
return table;
}
The inner construct has to be a while and not an if, and this is the most common defect in hand-written implementations. After falling back once, the shorter candidate may also mismatch, and there may be a shorter one still that works; the fallbacks form a chain and you must follow it until a character agrees or the length reaches zero. A single conditional gives a table that is correct on patterns with one repeated structure and quietly wrong on nested repetition.
The build is still linear. The length variable rises by at most one per outer iteration, so it rises at most m times in total, and since it never goes negative it can fall at most m times.
The search loop, and the shift after a full match
The search walks the text once, keeping a pattern index that falls back on mismatch exactly as the builder does. On a mismatch with a non-zero pattern index, set it to the table entry one before it and compare again without advancing the text. On a mismatch with the pattern index already zero, advance the text.
When the pattern index reaches m you have a match ending at the current text position, and here is the decision candidates get wrong: do not reset the pattern index to zero. Set it to the table entry for the last pattern position, which is the length of the longest border of the whole pattern. Resetting to zero misses overlapping occurrences — on the pattern aa against the text aaa there are two matches, and a reset finds one.
The overall bound is O of n plus m time and O of m space, and the argument for the text pass is the same accounting as for the build: the text index never decreases, and the pattern index rises at most once per text advance.
Being able to place KMP among its neighbours matters more than being able to write it from memory.
If you are searching for many patterns at once, running KMP once per pattern multiplies the text pass by the number of patterns. Aho-Corasick is the right structure: build a trie of all the patterns and add exactly this kind of fallback link to each node, pointing at the longest suffix of the current path that is also a prefix of some pattern. It is the same idea generalised from one string to a set, which is why it belongs in the same conversation as tries.
Rabin-Karp compares rolling hashes and only compares characters when hashes agree. Its expected cost is linear, its worst case is quadratic when hashes collide, and its advantage is that one pass can seek many patterns of the same length by testing the window's hash against a set. Boyer-Moore style methods, which scan the pattern from the right, skip more than one position at a time and beat linear in practice on long patterns over large alphabets.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).