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.