string matching
String matching is the problem of finding where a short pattern appears inside a longer text — exactly what happens when you press Ctrl-F and search a document. We call the text length n and the pattern length m. The honest, obvious method is the naive algorithm: line the pattern up at the first position of the text, compare character by character; if it matches, report it; if not, slide the pattern one step to the right and try again. Simple and correct.
The trouble is its worst case. Each of the roughly n starting positions can force up to m comparisons before a mismatch, so the naive approach costs O(nm) — and adversarial inputs like searching 'aaaab' inside a long run of 'aaaaaaaa…' actually hit that bound. The wasteful part is that after a partial match fails, the naive method throws away everything it just learned and restarts the pattern from scratch, re-examining text characters it has already seen.
The Knuth-Morris-Pratt algorithm (KMP) fixes exactly that waste, achieving O(n + m). Its key insight: when a mismatch happens partway through the pattern, the characters already matched are part of the pattern itself, so we often already know that a prefix of the pattern still lines up — there is no need to recheck it. KMP precomputes a small 'prefix table' (also called the failure function) that, for each position in the pattern, records the length of the longest prefix that is also a suffix ending there. Building the table costs O(m); then the text is scanned once, never stepping backward, for O(n). The idea is to remember, not to re-scan — and that turns a multiplication into an addition.
// naive O(n*m): re-checks text it has already seen
std::vector<int> findAll(const std::string& text,
const std::string& pat) {
std::vector<int> hits;
int n = text.size(), m = pat.size();
for (int i = 0; i + m <= n; ++i) { // each start position
int j = 0;
while (j < m && text[i + j] == pat[j]) ++j; // up to m compares
if (j == m) hits.push_back(i); // full match at i
}
return hits; // KMP avoids the restarts
}Naive matching is O(nm); KMP's prefix table brings it down to O(n + m).
KMP's prefix table (failure function) is the whole trick: it tells the search how far to safely jump the pattern after a mismatch, so the text is never re-scanned.