Run it
Both searches with their comparisons counted, on ordinary text and then on the repetitive input designed to make naive matching look bad. The gap is the argument for the table.
The naive approach, and its failure case
Correct, and O(nm) in the worst case.
The worst case is not artificial-looking but it is specific: text "aaaaaaaaab" with pattern "aaab". At every starting position the comparison matches three characters and fails on the fourth, so nearly all m comparisons happen n times.
| Text | Pattern | Comparisons |
|---|
| Random English | Any word | ~n — fails fast |
"a" * 10000 | "a" * 100 + "b" | ~1,000,000 |
"ab" * 5000 | "ab" * 100 + "c" | ~1,000,000 |
For most real text the naive method is fine, because mismatches happen on the first character. Repetitive data — DNA, binary formats, log files — is where it degrades, and that is what motivates the better algorithms.
KMP: never re-examine the text
Knuth-Morris-Pratt is O(n + m), and the idea is that a partial match already tells you something about the text. After matching "aab" and failing, there is no need to restart two positions later — the characters just read are known.
The machinery is the failure function: for each prefix of the pattern, the length of the longest proper prefix that is also a suffix.
For "ababaca":
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|
| char | a | b | a | b | a | c | a |
lps[i] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
lps[4] = 3 because "ababa" has "aba" as both a prefix and a suffix. On a mismatch after position 4, the pattern shifts so that "aba" lines up, rather than restarting.
The key property: i only ever increases. The text is read once.
What naive search wastes
Align the pattern at position 0, compare until a mismatch, then restart at position 1. The waste is that the comparisons already made are thrown away: on "aaaaaab" against "aaab", almost every alignment re-reads the same characters.
Worst case O(n·m). Average case on natural text is close to O(n), which is why naive search is a perfectly reasonable answer to give first — then improve it.
The prefix table
lps[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix of it. That overlap is exactly the information needed: after a mismatch, the characters already matched end in something that also begins the pattern, so the pattern can slide to that alignment without re-reading anything.
The table is built in O(m) using itself — on a mismatch while building, it falls back to lps[length-1] rather than restarting. That line looks wrong and is the reason the build is linear.
The property to state
i never decreases. Every character of the text is examined a bounded number of times, so the search is O(n) after an O(m) preprocessing pass.
Say what you would actually ship: text.find(pattern), which in CPython is a tuned hybrid of Boyer-Moore and Horspool. The point of implementing KMP is the reasoning, and interviewers know that.
Rabin-Karp: compare hashes, not characters
Hash the pattern once, then hash each window of the text and compare numbers. The trick is the rolling hash — the next window's hash is computed from the previous one in O(1) by removing the leading character and adding the trailing one.
O(n + m) expected, O(nm) worst case when hashes collide constantly.
The verification step is not optional. Equal hashes do not prove equal strings, so a confirming comparison is required — skipping it is a correctness bug, not an optimisation.
Rabin-Karp's real advantage is multiple pattern search: hash all the patterns into a set, and each window is one hash and one set lookup. That is what plagiarism detectors and rsync use.
Choosing between them
| Algorithm | Time | Space | Best for |
|---|
| Naive | O(nm) | O(1) | Short patterns, non-repetitive text |
| KMP | O(n+m) | O(m) | Guaranteed linear; streaming input |
| Rabin-Karp | O(n+m) expected | O(1) | Multiple patterns at once |
| Boyer-Moore | O(n/m) best | O(m+k) | Long patterns — what grep uses |
| Aho-Corasick | O(n + total) | O(total) | Many patterns simultaneously |
Boyer-Moore is the practical winner for long patterns and the counter-intuitive one: it compares the pattern right to left, so a mismatch on a character absent from the pattern lets it skip m positions at once. That makes it sublinear — it does not read every character of the text. Python's str.find uses a hybrid of Boyer-Moore-Horspool and a naive scan for short patterns.
Aho-Corasick generalises KMP to a set of patterns with one automaton, which is how intrusion-detection systems and virus scanners match thousands of signatures in one pass.
What to say in an interview
Start with the naive solution and its complexity — it is correct and takes thirty seconds. Then name the worst case concretely ("aaaaab" against "aab"), which shows you know why a better algorithm exists rather than that one does.
Then offer KMP, explain the failure function in one sentence, and write it if asked. If the follow-up is "what if there are many patterns?", the answer is Rabin-Karp or Aho-Corasick. If it is "what does the standard library do?", the answer is a Boyer-Moore variant.
Being able to say "in production I would call str.find, which is a tuned C implementation" is the right closing note — the exercise is about understanding, not about replacing the library.
What it is testing
Do you handle the empty pattern? It returns 0, and it is one line at the top.
Do you know the naive worst case? Naming a concrete repetitive input is the substance.
Do you verify after a hash match? Rabin-Karp without verification is wrong.
Do you understand the failure function? "The longest proper prefix that is also a suffix" — and why that lets the text pointer never move backwards.
Do you know what real implementations use? Boyer-Moore variants, chosen for skipping rather than for asymptotic tidiness.
Recap in one screen
- Naive search is O(nm), fine for ordinary text, and quadratic on repetitive input like
"aaaaab" against "aab". - KMP is O(n+m) using a failure function so the text pointer never rewinds.
- Rabin-Karp rolls a hash over each window in O(1) and must verify matches, since hashes collide.
- Boyer-Moore scans right to left and can skip m characters at a time, making it sublinear — which is why libraries use it.
- The empty pattern matches at index 0 by convention.