KMP Pattern Matching Algorithm in DSA Java - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

↩Return index Repeat until text ends

First build the LPS array for the pattern, then scan the text comparing characters. On mismatch, use LPS to shift pattern efficiently.

Execution Sample

DSA Java

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

This code builds the LPS array and uses it to find the pattern 'ABABC' in the text 'ABADBABC' efficiently.

Execution Table

Step	Operation	Text Index (i)	Pattern Index (j)	LPS Array	Action	Visual State
1	Build LPS array	-	-	[0,0,1,2,0]	Compute LPS for pattern 'ABABC'	LPS = [0,0,1,2,0]
2	Compare text[i] and pattern[j]	0	0	[0,0,1,2,0]	Match 'A'=='A', advance i,j	i=1, j=1
3	Compare text[i] and pattern[j]	1	1	[0,0,1,2,0]	Match 'B'=='B', advance i,j	i=2, j=2
4	Compare text[i] and pattern[j]	2	2	[0,0,1,2,0]	Match 'A'=='A', advance i,j	i=3, j=3
5	Compare text[i] and pattern[j]	3	3	[0,0,1,2,0]	Mismatch 'D'!='B', j = lps[j-1]=1	i=3, j=1
6	Compare text[i] and pattern[j]	3	1	[0,0,1,2,0]	Mismatch 'D'!='B', j = lps[j-1]=0	i=3, j=0
7	Compare text[i] and pattern[j]	3	0	[0,0,1,2,0]	Mismatch 'D'!='A', j=0, advance i	i=4, j=0
8	Compare text[i] and pattern[j]	4	0	[0,0,1,2,0]	Match 'B'=='A'?	i=4, j=0
9	Compare text[i] and pattern[j]	4	0	[0,0,1,2,0]	Mismatch 'B'!='A', j=0, advance i	i=5, j=0
10	Compare text[i] and pattern[j]	5	0	[0,0,1,2,0]	Match 'A'=='A', advance i,j	i=6, j=1
11	Compare text[i] and pattern[j]	6	1	[0,0,1,2,0]	Match 'B'=='B', advance i,j	i=7, j=2
12	Compare text[i] and pattern[j]	7	2	[0,0,1,2,0]	Mismatch 'C'!='A', j = lps[j-1]=0	i=7, j=0
13	Compare text[i] and pattern[j]	7	0	[0,0,1,2,0]	Mismatch 'C'!='A', j=0, advance i	i=8, j=0
14	End of text reached	8	0	[0,0,1,2,0]	No full pattern match found	Search ends

💡 Text fully scanned, no full pattern match found

Variable Tracker

Variable	Start	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	Final
i (text index)	0	1	2	3	3	3	4	4	5	6	7	7	8	8
j (pattern index)	0	1	2	3	1	0	0	0	0	1	2	0	0	0
LPS array	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]	[0,0,1,2,0]

Key Moments - 3 Insights

Why do we use the LPS array to update 'j' instead of resetting it to zero on mismatch?

Using the LPS array lets us skip unnecessary comparisons by jumping 'j' to the longest prefix suffix, as shown in steps 5-6 where 'j' moves back but not immediately to zero, saving time.

Why do we advance 'i' only when 'j' is zero on mismatch?

When 'j' is zero, no prefix matches, so we must move forward in text (step 7). If 'j' > 0, we shift pattern using LPS without moving 'i' (steps 5-6).

What happens if the pattern is found in the text?

When 'j' reaches pattern length, it means full match found. The code returns the start index (i-j). This is not shown in this example as no full match occurs.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'j' after step 5?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Pattern Index (j)' column at step 5 in the execution table.

At which step does the algorithm first use the LPS array to update 'j' after a mismatch?

A Step 4

B Step 5

C Step 8

D Step 10

💡 Hint

Look for the first step where 'Action' mentions 'j = lps[j-1]' in the execution table.

If the pattern was 'ABAB' instead of 'ABABC', how would the LPS array change?

A [0,0,1,2]

B [0,1,2,3]

C [0,0,0,0]

D [1,2,3,4]

💡 Hint

Recall how LPS array stores longest prefix suffix lengths for each prefix of the pattern.

Concept Snapshot

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

Full Transcript

The KMP Pattern Matching Algorithm first builds an LPS array for the pattern, which stores lengths of longest proper prefix which is also suffix for each prefix of the pattern. Then it scans the text with two indexes: i for text and j for pattern. When characters match, both indexes advance. On mismatch, if j is not zero, j is updated to lps[j-1] to skip unnecessary comparisons. If j is zero, i advances. When j reaches the pattern length, a full match is found. This process efficiently finds the pattern in the text without backtracking i.

Practice

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

easy

A. To count the number of vowels in a string

B. To sort characters in a string alphabetically

C. To reverse a string in linear time

D. To efficiently find occurrences of a pattern within a text

Solution

1. Step 1: Understand KMP's goal

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

2. Step 2: Compare with other options

   Sorting, reversing, or counting vowels are unrelated to pattern searching.

3. Final Answer:

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

4. Quick Check:

   KMP = Pattern Searching [OK]

Hint: KMP is about fast pattern search, not string modification [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP counts characters

2. Which of the following is the correct way to initialize the prefix array (lps) in the KMP algorithm in Java?

easy

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

B. int lps[] = new int[pattern.length() + 1];

C. int lps = new int[pattern.length()];

D. int[] lps = new int[pattern.length() - 1];

Solution

1. Step 1: Check array declaration syntax

   In Java, arrays are declared with type[], e.g., int[] lps.

2. Step 2: Check array size correctness

   Prefix array size equals pattern length, so new int[pattern.length()] is correct.

3. Final Answer:

   int[] lps = new int[pattern.length()]; -> Option A

4. Quick Check:

   Correct Java array init = int[] lps = new int[pattern.length()]; [OK]

Hint: Use int[] lps = new int[pattern.length()] for prefix array [OK]

Common Mistakes:

• Using incorrect array size (too big or too small)
• Wrong syntax like int lps instead of int[] lps
• Adding unnecessary +1 or -1 to length

3. What will be the output of the following Java code snippet using KMP to search pattern "ABABC" in text "ABABABCABABC"?

String text = "ABABABCABABC";
String pattern = "ABABC";
List<Integer> result = KMPSearch(pattern, text);
System.out.println(result);

Assume KMPSearch returns a list of starting indices where pattern is found.

medium

A. [1, 6]

B. [0, 5]

C. [2, 7]

D. [3, 8]

Solution

1. Step 1: Identify pattern occurrences in text

   Check text "ABABABCABABC" for "ABABC" starting indices: - At index 0: substring "ABABA" does not match fully - At index 2: substring "ABABC" matches fully - At index 5: substring "CABAB" does not match - At index 6: substring "ABABC" matches fully Actually, the pattern "ABABC" occurs at indices 2 and 7, but index 7 is out of range for the second match. Re-examining carefully: - At index 0: substring "ABABA" partial - At index 5: substring "CABAB" no - At index 6: substring "ABABC" matches - At index 7: substring "BABC" incomplete So matches at indices 2 and 6.

2. Step 2: Confirm no other matches

   Other indices do not match the full pattern exactly.

3. Final Answer:

   [2, 6] -> Option B

4. Quick Check:

   Pattern found at indices 2 and 6

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

Common Mistakes:

• Off-by-one errors in indexing
• Confusing partial matches as full matches
• Assuming matches start at 0 or 1 incorrectly

4. Consider this snippet of KMP prefix array (lps) computation in Java:

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

What is the bug in this code?

medium

A. Should increment i before assigning lps[i]

B. len should be reset to 0 instead of lps[len - 1]

C. No bug; code correctly computes lps array

D. Missing initialization of lps array before loop

Solution

1. Step 1: Analyze lps computation logic

   This code follows the standard KMP prefix array logic: - Increment len and assign lps[i] when chars match - Reset len using lps[len-1] when mismatch and len != 0 - Assign 0 and increment i when len == 0

2. Step 2: Verify no missing steps

   Initialization of lps array is assumed done before; loop logic is correct.

3. Final Answer:

   No bug; code correctly computes lps array -> Option C

4. Quick Check:

   Standard KMP lps logic = No bug; code correctly computes lps array [OK]

Hint: Standard KMP lps code is correct as given [OK]

Common Mistakes:

• Thinking i must increment before lps assignment
• Resetting len incorrectly to 0 instead of lps[len-1]
• Forgetting to initialize lps array before loop

5. Given the pattern "AABAACAABAA" and text "AABAACAABAABAABA", how many times will the KMP algorithm find the pattern in the text? Assume zero-based indexing and full matches only.

hard

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Search for pattern occurrences in text

   Check text "AABAACAABAABAABA" for pattern "AABAACAABAA": - At index 0: substring matches pattern fully - At index 7: substring "AABAACAABAA" matches fully - Other indices do not match fully

2. Step 2: Confirm matches

   Two full matches found at indices 0 and 7.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pattern appears twice fully [OK]

Hint: Count only full pattern matches in text [OK]

Common Mistakes:

• Counting partial matches as full matches
• Missing the first match at index 0
• Assuming overlapping partial matches count