KMP Pattern Matching Algorithm in DSA C# - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array

↓

Start matching text and pattern

↓

Compare characters

First build the LPS array for the pattern, then use it to efficiently match the pattern in the text by skipping unnecessary comparisons.

Execution Sample

DSA C#

int[] BuildLPS(string pattern) {
  int[] lps = new int[pattern.Length];
  int len = 0, i = 1;
  while (i < pattern.Length) {
    if (pattern[i] == pattern[len]) lps[i++] = ++len;
    else if (len != 0) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}

This code builds the LPS array which stores the longest prefix suffix lengths for the pattern.

Execution Table

Step	Operation	Pattern Index (i)	Length (len)	LPS Array State	Explanation
1	Initialize	i=1	len=0	[0, 0, 0, 0, 0]	Start building LPS array with i=1, len=0
2	Compare pattern[1] and pattern[0]	i=1	len=0	[0, 0, 0, 0, 0]	No match, len=0, set lps[1]=0, i++
3	Compare pattern[2] and pattern[0]	i=2	len=0	[0, 0, 0, 0, 0]	No match, len=0, set lps[2]=0, i++
4	Compare pattern[3] and pattern[0]	i=3	len=0	[0, 0, 0, 1, 0]	Match, len=1, set lps[3]=1, i++
5	Compare pattern[4] and pattern[1]	i=4	len=1	[0, 0, 0, 1, 2]	Match, len=2, set lps[4]=2, i++
6	LPS array complete	i=5	len=2	[0, 0, 0, 1, 2]	LPS array built for pattern
7	Start matching text and pattern	textIndex=0, patIndex=0	-	-	Begin scanning text with pattern
8	Compare text[0] and pattern[0]	patIndex=0	-	-	Match, advance both indexes
9	Compare text[1] and pattern[1]	patIndex=1	-	-	Match, advance both indexes
10	Compare text[2] and pattern[2]	patIndex=2	-	-	Mismatch, use lps to shift pattern
11	Shift pattern using lps[1]=0	patIndex=0	-	-	Reset patIndex to 0, textIndex stays
12	Compare text[2] and pattern[0]	patIndex=0	-	-	Match, advance both indexes
13	Compare text[3] and pattern[1]	patIndex=1	-	-	Match, advance both indexes
14	Compare text[4] and pattern[2]	patIndex=2	-	-	Match, advance both indexes
15	Compare text[5] and pattern[3]	patIndex=3	-	-	Match, advance both indexes
16	Compare text[6] and pattern[4]	patIndex=4	-	-	Match, pattern found at textIndex=2
17	Return match index	-	-	-	Pattern found, return starting index 2

💡 Pattern found at text index 2, matching complete

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 10	After Step 12	After Step 16	Final
i (pattern index for LPS)	1	2	4	5	-	-	-	-
len (length of longest prefix suffix)	0	0	1	2	-	-	-	-
lps array	[0, 0, 0, 0, 0]	[0, 0, 0, 0, 0]	[0, 0, 0, 1, 0]	[0, 0, 0, 1, 2]	-	-	-	-
textIndex (text scanning)	-	-	-	-	2	3	7	7
patIndex (pattern scanning)	-	-	-	-	2	0	5	5

Key Moments - 3 Insights

Why do we use the LPS array to shift the pattern instead of moving the text index?

Because the LPS array tells us the longest prefix which is also a suffix, so we can skip re-checking characters in the text and only move the pattern index, saving time. See step 10 and 11 in the execution_table.

Why does the pattern index reset to 0 after a mismatch at step 10?

Because lps[1] is 0, meaning no proper prefix suffix for that position, so we start matching pattern from the beginning again without moving the text index. See step 11.

How does the LPS array help avoid re-checking characters?

It stores lengths of longest proper prefix which is also suffix, so when mismatch happens, we know where to resume matching in the pattern without moving text index. See steps 4-6 for LPS build and steps 10-12 for usage.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of len and what does it represent?

A len=0, no prefix suffix found

B len=2, total matches found

C len=1, length of longest prefix suffix so far

D len=3, pattern index

💡 Hint

Check the 'Length (len)' column at step 4 in execution_table

At which step does the pattern first mismatch with the text?

A Step 8

B Step 10

C Step 12

D Step 14

💡 Hint

Look for 'Mismatch' in the Explanation column in execution_table

If the LPS array had a higher value at index 1, how would step 11 change?

A patIndex would reset to a higher value, skipping more comparisons

B patIndex would reset to 0 as usual

C textIndex would move forward skipping characters

D Matching would stop immediately

💡 Hint

Refer to how LPS array values affect pattern index shifts in steps 10-12

Concept Snapshot

KMP Pattern Matching Algorithm:
- Build LPS array for pattern to store longest prefix suffix lengths
- Use LPS to skip unnecessary comparisons during matching
- On mismatch, shift pattern using LPS without moving text index
- Achieves O(n) time matching
- Efficient for large texts and repeated patterns

Full Transcript

The KMP Pattern Matching Algorithm first builds an LPS array for the pattern, which stores the length of the longest prefix that is also a suffix for each position. This helps avoid re-checking characters in the text when a mismatch occurs. During matching, characters of the text and pattern are compared. On a match, both indexes advance. On mismatch, the pattern index shifts using the LPS array, while the text index stays, allowing efficient skipping. This process continues until the pattern is found or the text ends. The execution table shows step-by-step how the LPS array is built and how the matching proceeds, including pointer movements and decisions. Key moments clarify why the pattern shifts and how the LPS array optimizes matching. The visual quiz tests understanding of these steps. Overall, KMP is a fast and clever way to find patterns in text by using precomputed information to skip unnecessary checks.

Practice

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

easy

A. To find occurrences of a pattern string within a text efficiently

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To calculate the factorial of a number recursively

Solution

1. Step 1: Understand the goal of KMP

   KMP is designed to search for a pattern inside a larger text efficiently without rechecking characters unnecessarily.

2. Step 2: Compare with other options

   Sorting, reversing strings, and calculating factorials are unrelated to pattern searching.

3. Final Answer:

   To find occurrences of a pattern string within a text efficiently -> Option A

4. Quick Check:

   KMP = Pattern searching [OK]

Hint: KMP is all about fast pattern search in text [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates factorials

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

easy

A. int[] lps = new int();

B. int lps = new int[pattern.Length];

C. int lps[] = new int[pattern.Length];

D. int[] lps = new int[pattern.Length];

Solution

1. Step 1: Understand array declaration in C#

   In C#, arrays are declared with type[], then new type[size]. So int[] lps = new int[pattern.Length]; is correct.

2. Step 2: Check other options

   int lps = new int[pattern.Length]; misses [] for array type, C uses invalid syntax, D uses C/C++ style which is invalid in C#.

3. Final Answer:

   int[] lps = new int[pattern.Length]; -> Option D

4. Quick Check:

   C# array syntax = int[] name = new int[size]; [OK]

Hint: Use int[] for arrays, not int alone [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using C/C++ style array declaration in C#
• Trying to instantiate array without size

3. What will be the output of the following C# code snippet using KMP algorithm to find pattern "ABABC" in text "ABABABC"?

string text = "ABABABC";
string pattern = "ABABC";
List<int> matches = KMPSearch(pattern, text);
Console.WriteLine(string.Join(",", matches));

// Assume KMPSearch returns list of start indices where pattern matches text

medium

A. 0,2

B. 1

C. 2

D. No matches

Solution

1. Step 1: Analyze the text and pattern

   Text: A B A B A B C Pattern: A B A B C Check where pattern fully matches text starting index.

2. Step 2: Find matching index

   At index 0: text substring "ABABA" does not match "ABABC" (last char mismatch) At index 1: substring "BABAB" no match At index 2: substring "ABABC" matches pattern exactly.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substring matches carefully for exact pattern [OK]

Common Mistakes:

• Assuming multiple matches without checking full pattern
• Off-by-one errors in indexing
• Confusing partial matches as full matches

4. Identify the bug in this KMP prefix table (lps) computation code snippet in C#:

int[] ComputeLPS(string pattern) {
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;
    while (i < pattern.Length) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

medium

A. Incorrect update of length in else block: should be length = lps[length - 1];

B. Wrong initialization of lps array size

C. Using while loop instead of for loop causes infinite loop

D. Missing return statement at the end

Solution

1. Step 1: Understand lps update logic

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

2. Step 2: Check other parts

   Array size is correct, while loop is valid, return statement exists. So only length update is wrong.

3. Final Answer:

   Incorrect update of length in else block: should be length = lps[length - 1]; -> Option A

4. Quick Check:

   lps update uses length-1 index [OK]

Hint: Use length-1 index when updating length on mismatch [OK]

Common Mistakes:

• Using lps[length] instead of lps[length - 1]
• Confusing loop types causing infinite loops
• Forgetting to return lps array

5. Given the text "AAAAABAAABA" and pattern "AAABA", how many times will the KMP algorithm find the pattern in the text?

hard

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Identify all occurrences of pattern in text

   Text: A A A A A B A A A B A Pattern: A A A B A Check each possible start index:

2. Step 2: Check matches at each index

   Index 0: substring "AAAAA" no (pattern ends with B) Index 1: substring "AAAAB" no (pattern ends with A) Index 2: substring "AAABA" yes (match 1) Index 3: substring "AABAA" no Index 4: substring "ABAAA" no Index 5: substring "BAAAB" no Index 6: substring "AAABA" yes (match 2) Index 7: substring "AABA" incomplete Index 8: substring "ABA" incomplete Check carefully for overlapping matches.

3. Step 3: Re-check for missed matches

   Check index 1 carefully: substring "AAAAB" pattern is "AAABA" so no match. Check index 0 carefully: substring "AAAAA" pattern ends with B, no match. Check index 6: "AAABA" matches pattern exactly (match 2). Check index 2: "AAABA" matches pattern exactly (match 1). No other matches found.

4. Step 4: Check index 3 for overlapping match

   At index 3: substring "AABAA" does not match pattern "AAABA". At index 4: substring "ABAAA" no match. At index 5: substring "BAAAB" no match. At index 7: substring "AABA" incomplete. So total matches found: 2.

5. Final Answer:

   2 -> Option B

6. Quick Check:

   Pattern found twice in text [OK]

Hint: Check each substring carefully for full pattern match [OK]

Common Mistakes:

• Counting partial matches as full matches
• Missing overlapping matches
• Off-by-one errors in substring indexing