KMP Algorithm

Knuth-Morris-Pratt pattern matching and prefix function in O(n + m).

[Strings]|

Jul 9, 2026

|explanatory_notes.md|

#kmp#pattern-matching#prefix-function#string

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> prefixFunction(const string &s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; 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> kmpSearch(const string &text, const string &pat) {
    string t = pat + "#" + text;
    vector<int> pi = prefixFunction(t);
    vector<int> matches;
    int m = pat.size();
    for (int i = m + 1; i < (int)t.size(); i++)
        if (pi[i] == m)
            matches.push_back(i - 2 * m);
    return matches;
}

26 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

KMP Algorithm

Linear-time pattern matching using the prefix function to avoid redundant comparisons.

Prefix Function

For each position $i$ , $\pi[i]$ is the length of the longest proper prefix of $s[0..i]$ that is also a suffix:

\pi[i] = \max\{k : s[0..k-1] = s[i-k+1..i],\; k < i+1\}

Built in $O(n)$ by maintaining $j = \pi[i-1]$ and falling back via $j = \pi[j-1]$ on mismatch.

Pattern Matching

Build

t = p + \text{\#} + s

(sentinel prevents false overlaps)

Compute

\pi

t

Match at position

i - 2|p|

s

whenever

\pi[i] = |p|

When to Use

Finding all occurrences of pattern

p

in text

s

String periodicity —

s

has period

p

\pi[|s|-1] \ge |s| - p

and

p \mid |s|

Computing the prefix function for DP on strings, automaton construction

Complexity

Time —

O(n + m)

Space —

O(n + m)