KMP Pattern Matching Algorithm in DSA C++ - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

First, build the LPS array for the pattern. Then, scan the text comparing characters. On mismatch, use LPS to skip unnecessary comparisons. Repeat until all matches are found or text ends.

Execution Sample

DSA C++

int i = 0, j = 0;
while (i < n) {
  if (text[i] == pattern[j]) {
    i++; j++;
  } else if (j != 0) {
    j = lps[j-1];
  } else {
    i++;
  }
}

This code scans the text and pattern using indexes i and j, advancing or shifting j using the LPS array to find pattern matches efficiently.

Execution Table

Step	Operation	i (Text Index)	j (Pattern Index)	Comparison	Action	Match Found	Visual State
1	Compare text[0] and pattern[0]	0	0	'A' == 'A'	Match: i=1, j=1	No	Text: A B C D A B C D A B C D Pattern: A B C Indexes: i=0->1, j=0->1
2	Compare text[1] and pattern[1]	1	1	'B' == 'B'	Match: i=2, j=2	No	Indexes: i=1->2, j=1->2
3	Compare text[2] and pattern[2]	2	2	'C' == 'C'	Match: i=3, j=3	Yes at i-j=0	Pattern found at index 0
4	Reset j using LPS[j-1]	3	3	j= lps[2]=0	j=0	No	Prepare for next match
5	Compare text[3] and pattern[0]	3	0	'D' != 'A'	Mismatch: j=0, i=4	No	Move i forward
6	Compare text[4] and pattern[0]	4	0	'A' == 'A'	Match: i=5, j=1	No	Indexes: i=4->5, j=0->1
7	Compare text[5] and pattern[1]	5	1	'B' == 'B'	Match: i=6, j=2	No	Indexes: i=5->6, j=1->2
8	Compare text[6] and pattern[2]	6	2	'C' == 'C'	Match: i=7, j=3	Yes at i-j=4	Pattern found at index 4
9	Reset j using LPS[j-1]	7	3	j= lps[2]=0	j=0	No	Prepare for next match
10	Compare text[7] and pattern[0]	7	0	'D' != 'A'	Mismatch: j=0, i=8	No	Move i forward
11	Compare text[8] and pattern[0]	8	0	'A' == 'A'	Match: i=9, j=1	No	Indexes: i=8->9, j=0->1
12	Compare text[9] and pattern[1]	9	1	'B' == 'B'	Match: i=10, j=2	No	Indexes: i=9->10, j=1->2
13	Compare text[10] and pattern[2]	10	2	'C' == 'C'	Match: i=11, j=3	Yes at i-j=8	Pattern found at index 8
14	Reset j using LPS[j-1]	11	3	j= lps[2]=0	j=0	No	Prepare for next match
15	Compare text[11] and pattern[0]	11	0	'D' != 'A'	Mismatch: j=0, i=12	No	Move i forward
16	End	12	0	i=12 == n=12	Stop	No	Search complete

💡 i reaches text length 12, no more characters to compare

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	After Step 15	Final
i (Text Index)	0	1	2	3	3	4	5	6	7	7	8	9	10	11	11	12	12
j (Pattern Index)	0	1	2	3	0	0	1	2	3	0	0	1	2	3	0	0	0

Key Moments - 3 Insights

Why do we reset j to lps[j-1] instead of zero on mismatch?

Resetting j to lps[j-1] allows us to skip rechecking characters that we know match, saving time. See steps 4, 9, and 14 where j resets to 0 using LPS instead of restarting from zero.

Why don't we move i back when mismatch happens and j != 0?

We never move i backward because the LPS array tells us how much to shift the pattern. This keeps i moving forward steadily, as shown in steps 5 and 10 where i increments even on mismatch.

How do we know when a full pattern match is found?

When j equals the pattern length (3 here), it means all pattern characters matched. Steps 3, 8, and 13 show j reaching 3, indicating a match found at i-j index.

Visual Quiz - 3 Questions

Look at the execution table at step 3. What is the value of i and j after this step?

A i=3, j=3

B i=2, j=2

C i=3, j=0

D i=0, j=0

💡 Hint

Check the 'i (Text Index)' and 'j (Pattern Index)' columns in row for step 3.

At which step does the first pattern match get reported?

A Step 1

B Step 5

C Step 3

D Step 8

💡 Hint

Look at the 'Match Found' column for the first 'Yes' value.

If the LPS array was not used, what would happen to the value of i on mismatch at step 5?

A i would stay the same

B i would increase

C i would decrease

D i would reset to zero

💡 Hint

Observe that i always moves forward in the execution table even on mismatch.

Concept Snapshot

KMP Pattern Matching Algorithm:
- Precompute LPS (Longest Prefix Suffix) array for pattern
- Use two indexes: i for text, j for pattern
- On match: advance both i and j
- On mismatch: if j != 0, set j = lps[j-1], else advance i
- When j == pattern length, pattern found at i-j
- Efficiently skips unnecessary comparisons using LPS

Full Transcript

The KMP algorithm first builds an LPS array for the pattern to know how to skip characters on mismatch. It uses two indexes i and j to scan the text and pattern. When characters match, both indexes advance. On mismatch, if j is not zero, j resets to lps[j-1] to avoid rechecking matched characters. Otherwise, i advances. When j reaches the pattern length, a full match is found at index i-j in the text. This process repeats until the entire text is scanned. The execution table shows step-by-step how i and j change, when matches occur, and how the LPS array helps skip comparisons, making the search efficient.

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