Data Structures & Algorithms

KMP

Prefix-function based linear-time string matching with no backtracking in the text.

Category String Algorithms

Level basic

Source TeX + C++

stringspattern matchingprefix function

String Algorithms

KMP

The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.

Raw TeX

Overview

KMP is the classical linear-time pattern matcher built on the prefix function. Its main lesson is not ``use this one trick''. Its main lesson is that after a mismatch, we should not restart from scratch if some of the matched prefix is still usable.

That same prefix-function viewpoint also explains borders, periodicity, and several other string facts that show up in contest problems.

When to Use It

Use it when:

you need all occurrences of one pattern in one text,
you want a deterministic linear-time matcher,
hashing would be unnecessary or too fragile,
border information or periodicity is relevant, even if full matching is not.
For one casual substring check, the standard library is often enough. KMP matters when the prefix-function structure itself is useful.

Core Idea

For each position \(i\), the prefix function \(\pi[i]\) is the length of the longest proper prefix of the string that is also a suffix ending at \(i\).

That ``prefix equals suffix'' object is called a border. KMP uses borders as fallback positions: after a mismatch, the only remaining candidates are borders of what has already matched.

Key Insight

The invariant during the text scan is: the current matched length is the longest prefix of the pattern that is also a suffix of the processed text.

So if a mismatch happens after matching \(k\) characters, the next sensible candidate is not ``start over''. It is the longest border of that matched prefix, whose length is \(\pi[k - 1]\).

That is why no text character needs to be revisited from scratch.

Operations / Main Technique

The standard workflow is:

compute the prefix function of the pattern,
scan the text left to right,
on mismatch, fall back through prefix-function links,
on full match, report the occurrence and continue from the next border.

Worked example.

If the pattern prefix \(\texttt{abab}\) has matched and the next text character mismatches, KMP does not forget everything. The matched prefix has border \(\texttt{ab}\), so matching can continue as if those two characters had already been confirmed.

Correctness Intuition

At every step, the matched length is the longest possible viable prefix length. If a mismatch occurs, any longer candidate is impossible, so the next candidate must be the longest border of the current matched prefix. Repeating that step eventually finds the longest remaining candidate that could still continue the match.

Because the matched length only moves forward or falls back along prefix-function links, the total amount of fallback work is linear.

Complexity Analysis

prefix function of a length-\(n\) pattern: \(O(n)\),
scan of a length-\(m\) text: \(O(m)\),
total matching time: \(O(n + m)\),
memory: \(O(n)\).

Implementation

The reference code separates:

prefix_function(pattern),
kmp_search(text, pattern).
That split matters because many problems only need the prefix function itself. Matching is just one of its most famous applications.

Common Pitfalls

Confusing the prefix function with the Z-function.
Forgetting that \(\pi[i]\) is a proper prefix length.
Mishandling the empty-pattern edge case.
Writing the fallback loop incorrectly and skipping valid borders.
Treating KMP as only a matching tool and missing border/periodicity applications.

Variants / Extensions

prefix-function automaton style transitions,
border enumeration,
periodicity tests,
counting occurrences of every prefix,
comparison with the Z-function, which stores a different but related prefix-match view.
The Z-function often feels cleaner for some pattern tasks, but KMP is still the more natural language for borders and periodicity.

Practice Problems

Find all pattern occurrences in a long text.
Compute all borders of a string.
Detect the smallest repeating period of a string.
Problems that combine a small automaton with digit DP or DP on strings.

References

C++ competitive_programming/dsa/string-algorithms/kmp/code.cpp

Kept as a standalone source file so the implementation can be copied without TeX markup around it.

Raw file

vector<int> prefix_function(const string& s) {
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

vector<int> kmp_search(const string& text, const string& pattern) {
    if (pattern.empty()) return {};

    vector<int> pi = prefix_function(pattern);
    vector<int> occurrences;
    int matched = 0;

    for (int i = 0; i < (int)text.size(); ++i) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = pi[matched - 1];
        }
        if (text[i] == pattern[matched]) ++matched;
        if (matched == (int)pattern.size()) {
            occurrences.push_back(i - matched + 1);
            matched = pi[matched - 1];
        }
    }

    return occurrences;
}

Show raw files

Note TeXcompetitive_programming/dsa/string-algorithms/kmp/note.texC++ codecompetitive_programming/dsa/string-algorithms/kmp/code.cpp

KMP