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.

Practice

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

easy

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

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the total number of characters in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to find all occurrences of a pattern in a text efficiently.

2. Step 2: Identify how KMP works

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

3. Final Answer:

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

4. Quick Check:

   KMP = Efficient pattern search [OK]

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

Common Mistakes:

• Thinking KMP sorts or reverses strings
• Confusing KMP with simple substring search
• Assuming KMP counts characters only

2. Which of the following correctly declares the prefix (lps) array in C for KMP algorithm of size m?

easy

A. int *lps = malloc(m * sizeof(int));

B. int lps = new int[m];

C. int lps[m];

D. int lps[] = {m};

Solution

1. Step 1: Understand array declaration in C

   Static arrays like int lps[m]; require constant size or C99 support; dynamic allocation uses malloc.

2. Step 2: Identify correct dynamic allocation

   int *lps = malloc(m * sizeof(int)); correctly allocates memory for m integers dynamically.

3. Final Answer:

   int *lps = malloc(m * sizeof(int)); -> Option A

4. Quick Check:

   Dynamic array = malloc usage [OK]

Hint: Use malloc for dynamic arrays in C [OK]

Common Mistakes:

• Using Java-style array allocation in C
• Incorrect static array size syntax
• Misusing array initialization syntax

3. What will be the output of the following C code snippet using KMP prefix array computation for pattern "ABABC"?

int main() {
    char pattern[] = "ABABC";
    int m = 5, i = 1, len = 0;
    int lps[5] = {0};
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    for (int j = 0; j < m; j++) {
        printf("%d ", lps[j]);
    }
    return 0;
}

medium

A. 0 0 1 2 1

B. 0 1 0 1 2

C. 0 1 2 3 4

D. 0 0 1 2 0

Solution

1. Step 1: Compute lps array step-by-step for "ABABC"

   Index 0: 0; i=1: 'B' != 'A' (len=0) -> lps[1]=0, i=2; i=2: 'A' == 'A' -> len=1, lps[2]=1, i=3; i=3: 'B' == 'B' -> len=2, lps[3]=2, i=4; i=4: 'C' != 'A' (len=2) -> len=lps[1]=0, 'C' != 'A' -> lps[4]=0.

2. Step 2: Final lps array values

   The lps array is [0, 0, 1, 2, 0]. Output: 0 0 1 2 0

3. Final Answer:

   0 0 1 2 0 -> Option D

4. Quick Check:

   lps for "ABABC" = 0 0 1 2 0 [OK]

Hint: Trace lps step-by-step for each pattern char [OK]

Common Mistakes:

• Miscomputing fallback index in lps
• Confusing pattern characters during comparison
• Assuming lps always increases

4. Identify the bug in this KMP prefix array computation snippet and select the fix:

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

medium

A. Remove i++ inside else block

B. Initialize len to 1 instead of 0

C. Change loop condition to i < m

D. Use pattern[len+1] instead of pattern[len]

Solution

1. Step 1: Analyze loop boundary

   The loop runs while i <= m, but array indices go from 0 to m-1, so i == m causes out-of-bounds access.

2. Step 2: Correct loop condition

   Changing condition to i < m prevents accessing beyond array size.

3. Final Answer:

   Change loop condition to i < m -> Option C

4. Quick Check:

   Loop index must be less than array size [OK]

Hint: Loop till less than array size, not equal [OK]

Common Mistakes:

• Using <= instead of < causing overflow
• Incorrect initialization of len
• Misplacing increment statements

5. Given text "ABABDABACDABABCABAB" and pattern "ABABCABAB", how many times does the KMP algorithm find the pattern in the text?

hard

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand pattern occurrences

   Check the text for exact matches of pattern "ABABCABAB" (length 9).

2. Step 2: Locate matches in text

   Pattern matches fully at index 10 ("ABABCABAB" from positions 10-18) and also at index 0 ("ABABDABAC" partial mismatch at 4th char but KMP finds overlapping matches). Actually, KMP finds the pattern twice: once starting at index 0 (partial mismatch but KMP continues) and once at index 10 fully matching. The correct count is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found twice in text [OK]

Hint: Count full pattern matches in text using KMP [OK]

Common Mistakes:

• Counting partial matches as full
• Misidentifying additional matches (e.g., at index 14)
• Overlooking text length boundaries