KMP Pattern Matching Algorithm in DSA C++

Mental Model

KMP finds a pattern in text by skipping unnecessary checks using a precomputed table of longest prefix-suffix matches.

Analogy: Imagine searching for a word in a book by remembering parts of the word you already matched, so you don't start over from the beginning each time you find a mismatch.

Text:  A B C D A B C D A B C
Pattern:      A B C D A B
          ↑
Prefix Table: [0,0,0,0,1,2]

Dry Run Walkthrough

Input: text: 'ABABDABACDABABCABAB', pattern: 'ABABCABAB'

Goal: Find all starting indices where the pattern appears in the text

Step 1: Build prefix table for pattern

Pattern: A B A B C A B A B
Prefix Table: [0,0,1,2,0,1,2,3,4]

Why: Prefix table helps to know how far to jump on mismatch

Step 2: Start matching pattern at text index 0

Text: [A] B A B D A B A C D A B A B C A B A B
Pattern: [A] B A B C A B A B

Why: First characters match, continue

Step 3: Mismatch at text index 4 and pattern index 4 (D vs C), use prefix table to shift pattern

Pattern index shifted to 2 using prefix table
Text: A B A B [D] A B A C D A B A B C A B A B
Pattern:     A B A B C A B A B

Why: Avoid rechecking matched prefix, jump pattern index to 2

Step 4: Continue matching from text index 5 and pattern index 2

Text: A B A B D [A] B A C D A B A B C A B A B
Pattern:       A B C A B A B

Why: Characters match, continue

Step 5: Complete full pattern match at text index 10

Match found starting at index 10
Text: A B A B D A B A C D [A B A B C A B A B]
Pattern: A B A B C A B A B

Why: Pattern fully matched, record index

Result:

Pattern found at indices: 10

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

vector<int> kmpSearch(const string &text, const string &pattern) {
    if (pattern.empty()) {
        return {};
    }
    vector<int> prefix = buildPrefixTable(pattern);
    vector<int> result;
    int j = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == (int)pattern.size()) {
            result.push_back(i - j + 1);
            j = prefix[j - 1];
        }
    }
    return result;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    vector<int> matches = kmpSearch(text, pattern);
    for (int idx : matches) {
        cout << "Pattern found at index: " << idx << "\n";
    }
    return 0;
}

while (j > 0 && pattern[i] != pattern[j]) { j = prefix[j - 1]; }

On mismatch, jump pattern index back using prefix table to avoid rechecking

if (pattern[i] == pattern[j]) { j++; prefix[i] = j; }

On match, extend current longest prefix-suffix length

while (j > 0 && text[i] != pattern[j]) { j = prefix[j - 1]; }

On mismatch during search, jump pattern index back using prefix table

if (text[i] == pattern[j]) { j++; }

On match, move pattern index forward

if (j == (int)pattern.size()) { result.push_back(i - j + 1); j = prefix[j - 1]; }

When full pattern matched, record index and reset pattern index using prefix table

Output

Pattern found at index: 10

Complexity Analysis

Time: O(n + m) because we build prefix table in O(m) and search text in O(n) without backtracking

Space: O(m) for prefix table storing longest prefix-suffix lengths

vs Alternative: Naive search is O(n*m) because it restarts matching from scratch on mismatch; KMP skips redundant checks

Edge Cases

Empty pattern

Returns no matches immediately

DSA C++

if (pattern.empty()) return {};

Pattern longer than text

No matches found, search ends quickly

DSA C++

for (int i = 0; i < (int)text.size(); i++) { ... }

Pattern with repeated characters

Prefix table correctly handles repeated prefixes to skip checks

DSA C++

while (j > 0 && pattern[i] != pattern[j]) { j = prefix[j - 1]; }

When to Use This Pattern

When you need to find a pattern inside a text efficiently and want to avoid rechecking characters after mismatch, use KMP because it uses a prefix table to skip unnecessary comparisons.

Common Mistakes

Mistake: Not updating the pattern index j correctly after a mismatch using the prefix table
Fix: Always set j = prefix[j - 1] inside the mismatch while loop to jump back properly

Mistake: Forgetting to reset j after a full pattern match
Fix: After recording a match, set j = prefix[j - 1] to continue searching for overlapping matches

Summary

Finds all occurrences of a pattern in a text efficiently using a prefix table.

Use when you want fast pattern searching without rechecking characters after mismatches.

The key insight is precomputing longest prefix-suffix matches to skip redundant comparisons.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) algorithm in pattern matching?

easy

A. To find occurrences of a pattern in a text efficiently without rechecking characters

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the number of vowels in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to search for a pattern inside a text efficiently.

2. Step 2: Identify how it works

   It avoids rechecking characters by using a prefix table to skip unnecessary comparisons.

3. Final Answer:

   To find occurrences of a pattern in a text efficiently without rechecking characters -> Option A

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP skips repeated checks using prefix info [OK]

Common Mistakes:

• Thinking KMP sorts or modifies the text
• Confusing KMP with simple substring search
• Assuming KMP counts characters or vowels

2. Which of the following is the correct way to declare the prefix (lps) array in C++ for KMP algorithm?

easy

A. int lps[pattern_length];

B. int* lps = new int[pattern_length];

C. int lps = new int[pattern_length];

D. int lps[] = pattern_length;

Solution

1. Step 1: Understand dynamic array allocation in C++

   To create an array dynamically, use pointer with new keyword: int* lps = new int[size];

2. Step 2: Check options

   int* lps = new int[pattern_length]; correctly uses pointer and new to allocate array of given length.

3. Final Answer:

   int* lps = new int[pattern_length]; -> Option B

4. Quick Check:

   Dynamic array = int* lps = new int[size]; [OK]

Hint: Use int* with new[] for dynamic arrays in C++ [OK]

Common Mistakes:

• Using int lps = new int[] (wrong type)
• Declaring fixed size without initialization
• Incorrect array syntax like int lps[] = size

3. What will be the output of the following code snippet that uses KMP to find pattern occurrences?

std::string text = "ababcabcabababd";
std::string pattern = "ababd";
std::vector<int> result = kmpSearch(text, pattern);
for(int pos : result) std::cout << pos << " ";

Assuming kmpSearch returns all starting indices of pattern in text.

medium

A. 10

B. 0 5 10

C. 5 10

D. No output

Solution

1. Step 1: Identify pattern occurrences in text

   Check where "ababd" appears in "ababcabcabababd". It appears starting at index 10 only.

2. Step 2: Confirm output format

   kmpSearch returns vector of indices; printing them separated by space outputs "10 ".

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Pattern found at index 10 only [OK]

Hint: Scan text for exact pattern start index [OK]

Common Mistakes:

• Assuming multiple matches without checking text
• Confusing substring indices
• Printing no output if pattern not found

4. Consider this buggy code snippet for computing the LPS array in KMP:

void computeLPSArray(string pat, int M, int* lps) {
  int len = 0;
  lps[0] = 0;
  int i = 1;
  while (i < M) {
    if (pat[i] == pat[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len];  // Bug here
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
}

What is the bug and how to fix it?

medium

A. Replace while with for loop

B. Initialize len to 1 instead of 0

C. Remove else block completely

D. Change len = lps[len]; to len = lps[len - 1];

Solution

1. Step 1: Identify incorrect index in LPS update

   When mismatch occurs and len != 0, len should be updated to lps[len-1], not lps[len].

2. Step 2: Correct the assignment

   Change len = lps[len]; to len = lps[len - 1]; to avoid out-of-bound and logical error.

3. Final Answer:

   Change len = lps[len]; to len = lps[len - 1]; -> Option D

4. Quick Check:

   LPS update uses len-1 index [OK]

Hint: Use len-1 index when updating len in LPS [OK]

Common Mistakes:

• Using len index directly causes wrong LPS values
• Changing loop type unnecessarily
• Removing else block breaks logic

5. Given a text and multiple patterns, which approach best uses KMP to find all patterns efficiently?

hard

A. Run KMP separately for each pattern on the text

B. Concatenate all patterns and run KMP once

C. Build a trie of patterns and run Aho-Corasick algorithm

D. Use KMP only on the longest pattern

Solution

1. Step 1: Understand KMP's limitation

   KMP efficiently finds one pattern in text but running it repeatedly for many patterns is inefficient.

2. Step 2: Identify better multi-pattern method

   Building a trie and using Aho-Corasick algorithm finds all patterns simultaneously efficiently.

3. Final Answer:

   Build a trie of patterns and run Aho-Corasick algorithm -> Option C

4. Quick Check:

   Multi-pattern search = Aho-Corasick [OK]

Hint: Use Aho-Corasick for multiple patterns [OK]

Common Mistakes:

• Running KMP repeatedly wastes time
• Concatenating patterns confuses matching
• Ignoring specialized multi-pattern algorithms