Pattern Matching

KMP Algorithm

Precompute a 'failure function' that tells you where to resume matching after a mismatch, so you never backtrack in the text. Example: searching 'ABABC', if you fail at C, the failure function tells you to retry from position 2 (the second AB).

O(n + m)

O(m)

say this out loud

Naive matching rescans the text after every mismatch. KMP precomputes the prefix table so the text pointer never moves backwards, giving O(n plus m).

How It Works

Knuth-Morris-Pratt searches for a pattern in text without ever moving backward in the text. The key is the failure function (LPS array): for each prefix of the pattern, it stores the length of the longest proper prefix that is also a suffix. When a mismatch occurs after matching k characters, those k characters are known text. The failure function says how much of them still counts as a partial match, so matching resumes from lps[k-1] instead of restarting at zero.

Building the LPS array takes O(m) and the scan takes O(n), for O(n + m) total versus O(n·m) naive search. The text pointer never decreases, which also makes KMP suitable for streaming input.

Step-by-Step Visualization

Build the LPS array for the pattern "ababc". Each entry holds the length of the longest proper prefix that is also a suffix ending there

patternababc

1/9

Code

Java

static int kmpSearch(String text, String pattern) {
  int[] lps = buildLPS(pattern);
  int j = 0;
  for (int i = 0; i < text.length(); i++) {
    while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = lps[j - 1];
    if (text.charAt(i) == pattern.charAt(j)) j++;
    if (j == pattern.length()) return i - j + 1;
  }
  return -1;
}

static int[] buildLPS(String pattern) {
  int[] lps = new int[pattern.length()];
  int len = 0, i = 1;
  while (i < pattern.length()) {
    if (pattern.charAt(i) == pattern.charAt(len)) { lps[i++] = ++len; }
    else if (len > 0) { len = lps[len - 1]; }
    else { lps[i++] = 0; }
  }
  return lps;
}

Tips & Gotchas

1Build the failure/prefix function for the pattern first

2The failure function tells you where to resume matching after a mismatch

3Never re-examine characters in the text. Always make progress

Practice Problems

1Find the Index of the First Occurrence in a String
2Shortest Palindrome
3Repeated Substring Pattern
4Longest Happy Prefix

About the Pattern Matching Pattern

Find where a pattern string appears inside a text string. Naive approach is O(n·m). KMP and Z-Algorithm achieve O(n+m) by preprocessing the pattern to avoid re-scanning characters after a mismatch.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

What exactly does the failure function store?

For each index i, lps[i] is the length of the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch it tells you the longest partial match that is still alive, so you skip re-examining characters you have already matched.

When would I pick KMP over Rabin-Karp?

KMP gives a deterministic O(n + m) worst case with no collision risk, making it the safer choice for a single pattern. Rabin-Karp is preferable when hashing many candidate substrings at once, such as multi-pattern search or duplicate-substring detection.