KMP Pattern Matching Algorithm in DSA Python - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching pattern with text

↓

Compare characters

↓

End

First, build the LPS array for the pattern. Then, scan the text comparing characters. On mismatch, use LPS to shift pattern index without moving text index. Repeat until pattern found or text ends.

Execution Sample

DSA Python

def compute_lps(pattern):
    lps = [0]*len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length-1]
            else:
                lps[i] = 0
                i += 1
    return lps

This code builds the LPS array for the pattern, which helps skip unnecessary comparisons during matching.

Execution Table

Step	Operation	Pattern Index (j)	Text Index (i)	LPS Array	Action	Visual State
1	Build LPS array start	0	-	[0, 0, 0, 0, 0]	Initialize lps and pointers	Pattern: A B C A B LPS: 0 0 0 0 0
2	Compare pattern[1] and pattern[0]	1	-	[0, 0, 0, 0, 0]	No match, length=0, lps[1]=0, i=2	LPS: 0 0 0 0 0
3	Compare pattern[2] and pattern[0]	2	-	[0, 0, 0, 0, 0]	No match, length=0, lps[2]=0, i=3	LPS: 0 0 0 0 0
4	Compare pattern[3] and pattern[0]	3	-	[0, 0, 0, 1, 0]	Match, length=1, lps[3]=1, i=4	LPS: 0 0 0 1 0
5	Compare pattern[4] and pattern[1]	4	-	[0, 0, 0, 1, 2]	Match, length=2, lps[4]=2, i=5	LPS: 0 0 0 1 2
6	Start matching text	0	0	[0, 0, 0, 1, 2]	Compare text[0] and pattern[0]	Text: A B C A B C A B Pattern: A B C A B
7	Match text[0] and pattern[0]	1	1	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: A
8	Match text[1] and pattern[1]	2	2	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: A B
9	Match text[2] and pattern[2]	3	3	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: A B C
10	Match text[3] and pattern[3]	4	4	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: A B C A
11	Match text[4] and pattern[4]	5	5	[0, 0, 0, 1, 2]	Full pattern matched at index 0	Pattern found at text index 0
12	Continue matching	2	6	[0, 0, 0, 1, 2]	Mismatch at text[6], pattern[5]; shift pattern using LPS	Shift pattern index to 2
13	Match text[6] and pattern[2]	3	6	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: C
14	Match text[7] and pattern[3]	4	7	[0, 0, 0, 1, 2]	Characters match, advance both	Match so far: C A
15	Match text[8] and pattern[4]	5	8	[0, 0, 0, 1, 2]	Full pattern matched at index 3	Pattern found at text index 3
16	End	-	9	[0, 0, 0, 1, 2]	Text fully scanned	Matching complete

💡 Text fully scanned or pattern found at all possible positions

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 11	After Step 12	After Step 15	Final
lps	[0,0,0,0,0]	[0,0,0,1,0]	[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]
pattern_index (j)	0	3	4	5	2	5	-
text_index (i)	-	-	-	5	6	8	9
match_found_positions	[]	[]	[]	[0]	[0]	[0,3]	[0,3]

Key Moments - 3 Insights

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

Because the LPS array tells us the longest prefix which is also suffix, so we can avoid re-checking characters in the text that we know already matched. This is shown in step 12 where pattern_index shifts using LPS but text_index stays the same.

Why does the pattern index sometimes move backward during LPS computation?

When characters don't match during LPS building, we use the previous LPS value to try a smaller prefix. This avoids starting over from zero. See steps 2 and 3 where length stays 0 and lps[i] is set to 0.

How do we know when the full pattern is matched in the text?

When the pattern index reaches the length of the pattern (step 11 and 15), it means all characters matched consecutively. We then record the match position.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what is the LPS array value at index 4?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'LPS Array' column at step 5 in the execution_table

At which step does the first full pattern match occur in the text?

A Step 11

B Step 10

C Step 12

D Step 15

💡 Hint

Look for 'Full pattern matched' in the 'Action' column of execution_table

If the pattern index did not shift using LPS at step 12, what would happen to the text index?

A It would stay the same

B It would move forward by one

C It would move backward

D It would reset to zero

💡 Hint

Step 12 shows pattern index shifting without moving text index; without LPS, text index moves forward on mismatch

Concept Snapshot

KMP Pattern Matching Algorithm:
- Build LPS (Longest Prefix Suffix) array for pattern
- Use LPS to skip unnecessary comparisons
- Compare text and pattern characters
- On mismatch, shift pattern index using LPS, keep text index
- On full match, record position
- Efficiently finds all pattern occurrences in text

Full Transcript

The KMP Pattern Matching Algorithm first builds an LPS array for the pattern. This array helps to know how far to shift the pattern when a mismatch happens during matching. We then scan the text and pattern characters together. When characters match, we advance both indexes. When a mismatch occurs, instead of moving the text index forward, we use the LPS array to shift the pattern index to avoid re-checking characters. This process continues until the entire text is scanned or all pattern matches are found. The execution table shows step-by-step how the LPS array is built and how the matching proceeds, including pattern shifts and matches found.

Practice

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

easy

A. To calculate the factorial of a number recursively

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

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

Solution

1. Step 1: Understand the goal of KMP algorithm

   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 factorial calculations are unrelated to pattern searching.

3. Final Answer:

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

4. Quick Check:

   KMP = Pattern search [OK]

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

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates mathematical functions

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

easy

A. lps = [0] * len(pattern)

B. lps = []

C. lps = [1] * len(pattern)

D. lps = None

Solution

1. Step 1: Understand the prefix table initialization

   The prefix table (lps array) stores lengths of longest proper prefix which is also suffix for each prefix of the pattern. It must be initialized with zeros for all positions.

2. Step 2: Check each option

   lps = [0] * len(pattern) correctly initializes lps with zeros for the entire pattern length. lps = [] is empty list, which is incomplete. lps = [1] * len(pattern) initializes with ones, which is incorrect. lps = None sets None, which is invalid.

3. Final Answer:

   lps = [0] * len(pattern) -> Option A

4. Quick Check:

   Prefix table starts with zeros [OK]

Hint: Prefix table starts with zeros for all pattern chars [OK]

Common Mistakes:

• Initializing lps with ones instead of zeros
• Leaving lps empty
• Assigning None to lps

3. What will be the output of the following Python code snippet using KMP algorithm?

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

pattern = "ABABC"
lps = compute_lps(pattern)
print(lps)

medium

A. [1, 0, 1, 0, 1]

B. [0, 0, 1, 2, 0]

C. [0, 1, 2, 3, 4]

D. [0, 0, 0, 0, 0]

Solution

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

   Index 0: lps[0] = 0 (always zero)
   Index 1: pattern[1] = 'B' != pattern[0] = 'A', lps[1] = 0
   Index 2: pattern[2] = 'A' == pattern[0] = 'A', lps[2] = 1
   Index 3: pattern[3] = 'B' == pattern[1] = 'B', lps[3] = 2
   Index 4: pattern[4] = 'C' != pattern[2] = 'A', lps[4] = 0

2. Step 2: Final lps array

   The computed lps array is [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option B

4. Quick Check:

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

Hint: Match prefix and suffix lengths stepwise [OK]

Common Mistakes:

• Confusing lps values with pattern indices
• Assuming all zeros or all increasing values
• Mixing up characters when comparing

4. Identify the error in the following KMP prefix table computation code snippet:

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 0
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

medium

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

B. The lps array should be initialized with ones

C. The length variable should start at 1

D. The function should return pattern instead of lps

Solution

1. Step 1: Analyze the loop initialization

   In KMP prefix table computation, the first character's lps is always zero and we start comparing from the second character, so i should start at 1.

2. Step 2: Check the given code

   The code starts with i = 0, which causes comparing pattern[0] with pattern[0] immediately, leading to incorrect lps values and infinite loop risk.

3. Final Answer:

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

4. Quick Check:

   Start i at 1 for prefix table [OK]

Hint: Start prefix loop from second character (i=1) [OK]

Common Mistakes:

• Starting loop at zero causing wrong comparisons
• Initializing lps with ones instead of zeros
• Returning wrong variable

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

hard

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the pattern and text

   The pattern "ABABCABAB" is searched inside the text "ABABDABACDABABCABAB" using KMP which efficiently finds all occurrences.

2. Step 2: Identify pattern occurrences

   By scanning the text:
   - Occurrence starts at index 10 (substring "ABABCABAB")
   So pattern appears 1 time.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Pattern appears once in text [OK]

Hint: Count all pattern matches including overlaps [OK]

Common Mistakes:

• Counting only first occurrence
• Ignoring overlapping matches
• Misreading pattern or text