KMP — Failure Function & Pattern Matching

What does it solve?

Find every occurrence of a pattern P inside a text T. Naive matching restarts the pattern on every mismatch, wasting work. KMP never moves the text pointer backwards.

Key insight: precompute the failure function (LPS array): lps[i] is the length of the longest proper prefix of P[0..i] that is also a suffix. On a mismatch at pattern index j, jump to j = lps[j-1] instead of 0, reusing what already matched. Both phases are linear → O(N + M).

The core idea

// search with the failure function
i = 0, j = 0
while i < n:
  if T[i] == P[j]: i++, j++
    if j == m: report i-m; j = lps[j-1]
  elif j > 0: j = lps[j-1]
  else: i++

Complexity

Time complexity

O(N + M)

O(M) to build the LPS array, O(N) to scan the text. The text pointer i never decreases, so the search is strictly linear.

Space complexity

O(M)

The failure function stores one integer per pattern character. Nothing scales with the text length.

Examples & edge cases

Live animation — build the failure function, then search

Text & pattern

Failure function — lps[i] = longest proper prefix that is also a suffix

Current comparison

i = — j = — len = — matches = —

Step — of —

text index i

—

scanning text

pattern index j

—

matched prefix

prefix length

—

current border

matches found

—

occurrences

Pick a phase and press Play to start.

✓ Done

Speed Medium

Step-by-step table

C++ implementation

kmp.cpp

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

// Build the failure function (LPS = Longest Proper Prefix which is also Suffix)
vector<int> buildLPS(const string& p) {
    int m = p.size();
    vector<int> lps(m, 0);
    int len = 0;                 // length of the current longest border
    for (int i = 1; i < m; ) {
        if (p[i] == p[len]) {
            lps[i++] = ++len;      // extend the border
        } else if (len > 0) {
            len = lps[len - 1];    // fall back, don't reset to 0
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

// Return all start indices where p occurs in t
vector<int> kmpSearch(const string& t, const string& p) {
    vector<int> res, lps = buildLPS(p);
    int n = t.size(), m = p.size(), i = 0, j = 0;
    while (i < n) {
        if (t[i] == p[j]) {
            i++; j++;
            if (j == m) {          // full match
                res.push_back(i - m);
                j = lps[j - 1];    // keep going for overlaps
            }
        } else if (j > 0) {
            j = lps[j - 1];        // reuse matched prefix
        } else {
            i++;
        }
    }
    return res;
}

int main() {
    auto hits = kmpSearch("ABABDABACDABABCABAB", "ABABCABAB");
    for (int idx : hits) cout << idx << " "; // 10
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars