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

↓

Move both i,j

↓

If j == pattern length

↓

Pattern found at i-j

↓

Continue until text end

First build the LPS array for the pattern, then scan the text comparing characters. On mismatch, use LPS to avoid rechecking matched characters.

Execution Sample

DSA C

void KMPSearch(char* pat, char* txt) {
  int M = strlen(pat);
  int N = strlen(txt);
  int lps[M];
  computeLPSArray(pat, M, lps);
  int i = 0, j = 0;
  while (i < N) {
    if (pat[j] == txt[i]) { i++; j++; }
    if (j == M) { printf("Found at %d\n", i-j); j = lps[j-1]; }
    else if (i < N && pat[j] != txt[i]) {
      if (j != 0) j = lps[j-1]; else i++;
    }
  }
}

This code searches for pattern occurrences in text using the KMP algorithm with an LPS array to skip unnecessary comparisons.

Execution Table

Step	Operation	i (text index)	j (pattern index)	LPS Used	Action	Match Found	Visual State
1	Build LPS array	-	-	-	Compute LPS for pattern 'ABABCABAB' in text 'ABABDABACDABABCABAB'	-	LPS = [0,0,1,2,0,1,2,3,4]
2	Start matching	0	0	-	Compare txt[0]='A' and pat[0]='A'	Yes	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
3	Match	1	1	-	Characters match, increment i and j	No	i=1, j=1
4	Match	2	2	-	Characters match, increment i and j	No	i=2, j=2
5	Match	3	3	-	Characters match, increment i and j	No	i=3, j=3
6	Match	4	4	-	Characters match, increment i and j	No	i=4, j=4
7	Mismatch	4	4	lps[3]=2	Mismatch at txt[4]='D' vs pat[4]='C', use LPS to shift j=2	No	i=4, j=2
8	Mismatch	4	2	lps[1]=0	Mismatch at txt[4]='D' vs pat[2]='A', use LPS to shift j=0	No	i=4, j=0
9	Mismatch	4	0	-	j=0 and mismatch, increment i	No	i=5, j=0
10	Match	5	0	-	Characters match, increment i and j	No	i=6, j=1
11	Match	6	1	-	Characters match, increment i and j	No	i=7, j=2
12	Match	7	2	-	Characters match, increment i and j	No	i=8, j=3
13	Mismatch	8	3	lps[2]=1	Mismatch at txt[8]='C' vs pat[3]='B', use LPS to shift j=1	No	i=8, j=1
14	Mismatch	8	1	lps[0]=0	Mismatch at txt[8]='C' vs pat[1]='B', use LPS to shift j=0	No	i=8, j=0
15	Mismatch	8	0	-	j=0 and mismatch, increment i	No	i=9, j=0
16	Mismatch	9	0	-	j=0 and mismatch txt[9]='D' vs pat[0]='A', increment i	No	i=10, j=0
17	Pattern found	19	9	-	Characters match till j == 9 at i=19, pattern found at 19-9=10	Yes	Pattern found at index 10
18	Shift pattern	19	9	lps[8]=4	Set j = lps[8]=4 to continue searching	No	i=19, j=4
19	End	19	4	-	i reached text length, stop	No	Search complete

💡 i reached text length 19, no more characters to match

Variable Tracker

Variable	Start	After Step 6	After Step 9	After Step 12	After Step 16	After Step 17	Final
i (text index)	0	4	5	8	10	19	19
j (pattern index)	0	4	0	3	0	9	4
LPS array	N/A	Computed	Computed	Computed	Computed	Computed	Computed

Key Moments - 3 Insights

Why do we use the LPS array when a mismatch happens instead of moving i forward?

Because the LPS array tells us the longest prefix that is also a suffix, so we can shift the pattern without rechecking characters, as shown in step 7 where j moves from 4 to 2 without incrementing i.

Why do we sometimes move j back but not i when a mismatch occurs?

Because i points to the text and we only move it forward when we have no partial match to reuse. When mismatch happens, j moves back using LPS to reuse previous matches, as in step 7 and 13.

What does it mean when j equals the pattern length?

It means the entire pattern matched in the text ending at index i-1. We found a pattern occurrence at i-j, as shown in step 17.

Visual Quiz - 3 Questions

Look at the execution table at step 8. What happens to the indices i and j?

A i increments, j resets to 0 using LPS

B i stays the same, j resets to 0 using LPS

C Both i and j increment

D Both i and j reset to 0

💡 Hint

Check the 'Action' and 'i (text index)', 'j (pattern index)' columns at step 8.

At which step is the pattern found in the text according to the execution table?

A Step 13

B Step 16

C Step 17

D Step 19

💡 Hint

Look for the row where 'Match Found' is 'Yes' and 'Action' mentions pattern found.

If the LPS array was all zeros, how would the matching process change?

A The pattern would shift by one on mismatch, no reuse of previous matches

B The pattern would shift by the full length on mismatch

C The pattern would never shift and cause infinite loop

D The pattern would match instantly

💡 Hint

Refer to the 'LPS Used' column and how it affects shifting in the execution table.

Concept Snapshot

KMP Pattern Matching Algorithm:
- Precompute LPS (Longest Prefix Suffix) array for pattern
- Use LPS to skip unnecessary comparisons on mismatch
- Compare text and pattern characters with indices i, j
- On match: increment both i and j
- On mismatch: if j != 0, set j = lps[j-1], else increment i
- When j == pattern length, pattern found at i-j
- Efficiently finds all occurrences in O(N) time

Full Transcript

The KMP Pattern Matching Algorithm first builds an LPS array for the pattern, which stores the longest prefix that is also a suffix for each prefix of the pattern. Then it scans the text with two indices: i for text and j for pattern. When characters match, both indices move forward. On mismatch, instead of moving i forward blindly, the algorithm uses the LPS array to shift the pattern index j to reuse previous matches, avoiding rechecking characters. When j reaches the pattern length, it means the pattern is found in the text at position i-j. This process continues until the entire text is scanned. The LPS array is key to the algorithm's efficiency, allowing it to run in linear time relative to the text length.