KMP Pattern Matching Algorithm in DSA Go - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

↓

Pattern found

First, build the LPS array for the pattern. Then, compare characters of text and pattern, advancing indexes on match. On mismatch, use LPS to shift pattern without moving text index. Repeat until pattern is found or text ends.

Execution Sample

DSA Go

text := "ABABDABACDABABCABAB"
pattern := "ABABCABAB"
lps := buildLPS(pattern)
index := KMPSearch(text, pattern, lps)

This code builds the LPS array for the pattern and searches for the pattern in the text using the KMP algorithm.

Execution Table

Step	Operation	Text Index (i)	Pattern Index (j)	LPS Used	Action	Match Found Indices	Visual State
1	Build LPS array	-	-	-	Compute LPS for pattern "ABABCABAB"	-	LPS: [0,0,1,2,0,1,2,3,4]
2	Compare text[i] and pattern[j]	0	0	-	Match 'A' == 'A', advance i and j	-	Text: A B A B D ... Pattern: A B A B C ... i=1, j=1
3	Compare text[i] and pattern[j]	1	1	-	Match 'B' == 'B', advance i and j	-	i=2, j=2
4	Compare text[i] and pattern[j]	2	2	-	Match 'A' == 'A', advance i and j	-	i=3, j=3
5	Compare text[i] and pattern[j]	3	3	-	Match 'B' == 'B', advance i and j	-	i=4, j=4
6	Compare text[i] and pattern[j]	4	4	-	Mismatch 'D' != 'C', use LPS[j-1]=LPS[3]=2 to shift pattern	-	i=4, j=2
7	Compare text[i] and pattern[j]	4	2	-	Mismatch 'D' != 'A', use LPS[j-1]=LPS[1]=0 to shift pattern	-	i=4, j=0
8	Compare text[i] and pattern[j]	4	0	-	Mismatch 'D' != 'A', advance i	-	i=5, j=0
9	Compare text[i] and pattern[j]	5	0	-	Match 'A' == 'A', advance i and j	-	i=6, j=1
10	Compare text[i] and pattern[j]	6	1	-	Match 'B' == 'B', advance i and j	-	i=7, j=2
11	Compare text[i] and pattern[j]	7	2	-	Match 'A' == 'A', advance i and j	-	i=8, j=3
12	Compare text[i] and pattern[j]	8	3	-	Mismatch 'C' != 'B', use LPS[j-1]=LPS[2]=1 to shift pattern	-	i=8, j=1
13	Compare text[i] and pattern[j]	8	1	-	Mismatch 'C' != 'B', use LPS[j-1]=LPS[0]=0 to shift pattern	-	i=8, j=0
14	Compare text[i] and pattern[j]	8	0	-	Mismatch 'C' != 'A', advance i	-	i=9, j=0
15	Compare text[i] and pattern[j]	9	0	-	Mismatch 'D' != 'A', advance i	-	i=10, j=0
16	Compare text[i] and pattern[j]	10	0	-	Match 'A' == 'A', advance i and j	-	i=11, j=1
17	Compare text[i] and pattern[j]	11	1	-	Match 'B' == 'B', advance i and j	-	i=12, j=2
18	Compare text[i] and pattern[j]	12	2	-	Match 'A' == 'A', advance i and j	-	i=13, j=3
19	Compare text[i] and pattern[j]	13	3	-	Match 'B' == 'B', advance i and j	-	i=14, j=4
20	Compare text[i] and pattern[j]	14	4	-	Match 'C' == 'C', advance i and j	-	i=15, j=5
21	Compare text[i] and pattern[j]	15	5	-	Match 'A' == 'A', advance i and j	-	i=16, j=6
22	Compare text[i] and pattern[j]	16	6	-	Match 'B' == 'B', advance i and j	-	i=17, j=7
23	Compare text[i] and pattern[j]	17	7	-	Match 'A' == 'A', advance i and j	-	i=18, j=8
24	Compare text[i] and pattern[j]	18	8	-	Match 'B' == 'B', pattern fully matched	Pattern found at index 10	Match at i=18, j=8
25	End	18	8	-	Pattern found, stop	Pattern found at index 10	Search complete

💡 Pattern fully matched at text index 18 with pattern index 8, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 8	After Step 16	After Step 24	Final
i (text index)	0	1	4	5	11	18	18
j (pattern index)	0	1	2	0	1	8	8
LPS array	-	[0,0,1,2,0,1,2,3,4]	[0,0,1,2,0,1,2,3,4]	[0,0,1,2,0,1,2,3,4]	[0,0,1,2,0,1,2,3,4]	[0,0,1,2,0,1,2,3,4]	[0,0,1,2,0,1,2,3,4]
Match Found Indices	None	None	None	None	None	10	10

Key Moments - 3 Insights

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

Using the LPS array allows us to avoid re-checking characters in the text that we know already matched. This is shown in steps 6 and 7 where the pattern index j shifts using LPS but the text index i stays the same, saving time.

What happens when the pattern index j becomes zero after a mismatch?

When j becomes zero, it means no prefix matched so we must advance the text index i to check the next character. This is shown in step 8 where j resets to 0 and i increments.

How do we know when the pattern is fully matched?

The pattern is fully matched when j reaches the length of the pattern. In step 24, j=8 (pattern length -1) and the match is found at text index 10.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of j (pattern index) after step 6?

A 4

B 0

C 2

D 1

💡 Hint

Check the 'Pattern Index (j)' column in row for step 6.

At which step does the pattern fully match the text?

A Step 18

B Step 24

C Step 20

D Step 12

💡 Hint

Look for the row where 'Pattern fully matched' is mentioned in the 'Action' column.

If the LPS array was not used, what would happen to the text index i on mismatch?

A It would always advance by one

B It would stay the same

C It would move back

D It would jump to the end

💡 Hint

Refer to the 'Action' column in steps where mismatch occurs and LPS is used to avoid advancing i unnecessarily.

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 two indexes i, j
- On match: advance both i and j
- On mismatch: shift j using LPS, or advance i if j=0
- Pattern found when j == pattern length

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 compares characters of the text and pattern using two indexes i and j. When characters match, both indexes advance. On mismatch, the algorithm uses the LPS array to shift the pattern index j to avoid re-checking characters, while the text index i stays the same. If j becomes zero, the text index i advances. The pattern is found when j reaches the pattern length. This process efficiently finds the pattern in the text without backtracking the text index.

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 number of vowels in the text

Solution

1. Step 1: Understand KMP's goal

   KMP is designed to find pattern matches in text efficiently by avoiding repeated comparisons.

2. Step 2: Compare options with KMP's function

   Only To efficiently find occurrences of a pattern in a text without rechecking characters describes this efficient search without rechecking characters.

3. Final Answer:

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

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP avoids rechecking characters during pattern search [OK]

Common Mistakes:

• Thinking KMP sorts or modifies the text
• Confusing KMP with simple substring search
• Assuming KMP counts characters instead of searching

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

easy

A. lps := []string{len(pattern)}

B. lps := make([]int, len(pattern))

C. lps := make([]bool, len(pattern))

D. lps := new(int)

Solution

1. Step 1: Identify correct Go syntax for integer slice

   In Go, make([]int, size) creates an integer slice of given size.

2. Step 2: Check options for correct slice creation

   lps := make([]int, len(pattern)) correctly creates an int slice for lps. Others use wrong types or syntax.

3. Final Answer:

   lps := make([]int, len(pattern)) -> Option B

4. Quick Check:

   Go slice for lps = make([]int, len(pattern)) [OK]

Hint: Use make([]int, size) to create integer slices in Go [OK]

Common Mistakes:

• Using wrong slice type like []string or []bool
• Using new(int) which creates a pointer, not slice
• Incorrect slice initialization syntax

3. What will be the output of the following Go code snippet that uses KMP to find pattern occurrences?

package main
import "fmt"

func computeLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

func main() {
    pattern := "ABABC"
    lps := computeLPS(pattern)
    fmt.Println(lps)
}

medium

A. [0 0 0 0 0]

B. [0 1 2 3 4]

C. [1 2 3 4 5]

D. [0 0 1 2 0]

Solution

1. Step 1: Compute LPS array for pattern "ABABC"

   Check characters stepwise: - i=1: 'B' != 'A' => lps[1]=0 - i=2: 'A' == 'A' => length=1, lps[2]=1 - i=3: 'B' == 'B' => length=2, lps[3]=2 - i=4: 'C' != 'A' => length=lps[1]=0, lps[4]=0

2. Step 2: Final LPS array is [0, 0, 1, 2, 0]

   This matches [0 0 1 2 0] exactly.

3. Final Answer:

   [0 0 1 2 0] -> Option D

4. Quick Check:

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

Hint: Trace pattern chars to build LPS stepwise [OK]

Common Mistakes:

• Confusing LPS values with pattern indices
• Not resetting length correctly on mismatch
• Assuming all zeros or increasing sequence

4. Identify the bug in this KMP prefix table computation code snippet in Go:

func computeLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 0
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

medium

A. The function should return a string, not []int

B. The length variable should be initialized to 1

C. The loop should start with i = 1, not 0

D. The lps array should be of type []bool

Solution

1. Step 1: Check loop initialization for LPS computation

   In KMP, i starts from 1 because lps[0] is always 0 and no comparison needed at index 0.

2. Step 2: Identify incorrect i initialization

   Here i starts at 0, causing incorrect comparisons and possible infinite loop.

3. Final Answer:

   The loop should start with i = 1, not 0 -> Option C

4. Quick Check:

   Start i=1 for LPS loop [OK]

Hint: LPS loop always starts at index 1 [OK]

Common Mistakes:

• Starting loop at 0 causing wrong LPS values
• Initializing length incorrectly
• Wrong return type or array type

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

hard

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Understand the pattern and text

   The pattern "ABABCABAB" appears in the text at indices 10 and 12 (0-based indexing), overlapping occurrences.

2. Step 2: Count occurrences using KMP logic

   KMP finds two matches without rechecking characters, so total occurrences = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pattern occurs twice in text [OK]

Hint: Use KMP to find all pattern matches efficiently [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Overcounting occurrences
• Assuming zero matches due to complexity