KMP Pattern Matching Algorithm in DSA Rust - Execution Trace

Concept Flow - KMP Pattern Matching Algorithm

Build LPS array for pattern

↓

Start matching text and pattern

↓

Compare characters

First build the LPS array for the pattern, then scan the text comparing characters. On mismatch, use LPS to skip unnecessary comparisons.

Execution Sample

DSA Rust

pattern = "ABABC"
text = "ABABABC"
lps = build_lps(pattern)
i = 0
j = 0
while i < len(text):
  if text[i] == pattern[j]:
    i += 1
    j += 1
  else:
    if j != 0:
      j = lps[j-1]
    else:
      i += 1
  if j == len(pattern):
    return i - j

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

Execution Table

Step	Operation	Text Index (i)	Pattern Index (j)	LPS Used	Action	Match Found	Visual State
1	Build LPS array	-	-	-	LPS = [0,0,1,2,0]	-	-
2	Compare text[i] and pattern[j]	0	0	-	Match 'A' == 'A', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
3	Compare text[i] and pattern[j]	1	1	-	Match 'B' == 'B', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
4	Compare text[i] and pattern[j]	2	2	-	Match 'A' == 'A', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
5	Compare text[i] and pattern[j]	3	3	-	Match 'B' == 'B', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
6	Compare text[i] and pattern[j]	4	4	-	Mismatch 'A' != 'C', use LPS[j-1]=2	No	Text: A B A B A B C ^ Pattern: A B A B C ^
7	Adjust pattern index using LPS	4	2	2	Set j = 2, no advance i	No	Text: A B A B A B C ^ Pattern: A B A B C ^
8	Compare text[i] and pattern[j]	4	2	-	Match 'A' == 'A', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
9	Compare text[i] and pattern[j]	5	3	-	Match 'B' == 'B', advance i,j	No	Text: A B A B A B C ^ Pattern: A B A B C ^
10	Compare text[i] and pattern[j]	6	4	-	Match 'C' == 'C', advance i,j	Yes	Text: A B A B A B C ^ Pattern: A B A B C ^
11	Pattern found	7	5	-	Return index i-j = 2	Yes	Pattern found at index 2
12	End	7	5	-	Stop search	-	-

💡 Pattern found at index 2 in text, search stops

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

Key Moments - 3 Insights

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

Because the LPS array tells us the longest prefix which is also suffix, so we can skip unnecessary comparisons and avoid restarting from zero. See step 6 and 7 where j resets to 2, not zero.

Why does 'i' (text index) not move forward when we reset 'j' using LPS?

Because the mismatch happened at pattern index 'j', but the text character at 'i' might still match the new pattern index after shifting. So we keep 'i' fixed to re-compare. See step 7.

How do we know when the pattern is found in the text?

When 'j' reaches the length of the pattern, it means all characters matched. See step 10 and 11 where j=5 equals pattern length.

Visual Quiz - 3 Questions

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

A 4

B 0

C 2

D 5

💡 Hint

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

At which step does the pattern get fully matched in the text?

A Step 10

B Step 6

C Step 8

D Step 12

💡 Hint

Look for the step where 'Match Found' is 'Yes' and j equals pattern length.

If the LPS array was all zeros, how would the algorithm behave on mismatch?

A It would find matches faster

B It would reset j to zero and advance i every mismatch

C It would skip some characters in text

D It would never reset j

💡 Hint

Refer to the 'LPS Used' and 'Action' columns in the execution table, especially steps 6 and 7.

Concept Snapshot

KMP Pattern Matching Algorithm
- Build LPS (Longest Prefix Suffix) array for pattern
- Use LPS to skip unnecessary comparisons on mismatch
- Compare text and pattern characters with indices i, j
- On match: advance both i and j
- On mismatch: if j>0, set j = LPS[j-1], else advance i
- Pattern found when j == pattern length

Full Transcript

The KMP algorithm first builds an LPS array for the pattern, which stores the length of the longest prefix that is also a suffix for each prefix of the pattern. Then it scans the text with two indices: i for text and j for pattern. When characters match, both indices advance. On mismatch, instead of restarting from zero, the algorithm uses the LPS array to reset j to a smaller index, allowing skipping of redundant comparisons. This process continues until the pattern is found or the text ends. The execution table shows each step with indices, actions, and the visual state of matching. Key moments clarify why LPS is used and how indices move. The visual quiz tests understanding of index changes and pattern detection. This method efficiently finds patterns in text with O(n) time complexity.

Practice

1. What is the main purpose of the KMP Pattern Matching Algorithm?

easy

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

B. To sort an array of numbers quickly

C. To reverse a string in linear time

D. To calculate the factorial of a number

Solution

1. Step 1: Understand the problem KMP solves

   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 A

4. Quick Check:

   KMP = Pattern search [OK]

Hint: KMP is about searching patterns fast 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 declare the prefix table (lps array) in Rust for KMP algorithm?

easy

A. let mut lps = Vec::new();

B. let lps = [0; pattern.len()];

C. let lps: Vec<i32> = Vec::with_capacity(pattern.len());

D. let mut lps: Vec<usize> = vec![0; pattern.len()];

Solution

1. Step 1: Understand prefix table initialization

   The prefix table (lps) needs to be mutable and initialized with zeros for the length of the pattern.

2. Step 2: Check each option

   let mut lps: Vec<usize> = vec![0; pattern.len()]; correctly creates a mutable vector of usize with zeros. let lps = [0; pattern.len()]; creates an array but Rust arrays need constant size. let mut lps = Vec::new(); creates an empty vector without size. let lps: Vec<i32> = Vec::with_capacity(pattern.len()); creates a vector with capacity but no elements initialized.

3. Final Answer:

   let mut lps: Vec<usize> = vec![0; pattern.len()]; -> Option D

4. Quick Check:

   Mutable zero-filled vector = let mut lps: Vec<usize> = vec![0; pattern.len()]; [OK]

Hint: Use mutable vector with zeros sized to pattern length [OK]

Common Mistakes:

• Using fixed-size arrays without constant size
• Not initializing vector elements
• Using wrong data types for lps

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

fn main() {
    let text = "ABABABCABABC";
    let pattern = "ABABC";
    let positions = kmp_search(text, pattern);
    println!("{:?}", positions);
}

fn kmp_search(text: &str, pattern: &str) -> Vec<usize> {
    let lps = compute_lps(pattern);
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < text.len() {
        if text.as_bytes()[i] == pattern.as_bytes()[j] {
            i += 1;
            j += 1;
            if j == pattern.len() {
                result.push(i - j);
                j = lps[j - 1];
            }
        } else if j > 0 {
            j = lps[j - 1];
        } else {
            i += 1;
        }
    }
    result
}

fn compute_lps(pattern: &str) -> Vec<usize> {
    let mut lps = vec![0; pattern.len()];
    let mut length = 0;
    let mut i = 1;
    while i < pattern.len() {
        if pattern.as_bytes()[i] == pattern.as_bytes()[length] {
            length += 1;
            lps[i] = length;
            i += 1;
        } else if length > 0 {
            length = lps[length - 1];
        } else {
            lps[i] = 0;
            i += 1;
        }
    }
    lps
}

medium

A. [0, 5, 7]

B. [2, 7]

C. [2, 7, 9]

D. [0, 5]

Solution

1. Step 1: Understand KMP search output

   The function returns starting indices where the pattern "ABABC" appears in the text "ABABABCABABC".

2. Step 2: Trace pattern matches

   Pattern matches at index 2 ("ABABC" in "ABABABC") and index 7 ("ABABC" in "ABABC"), so output is [2, 7].

3. Final Answer:

   [2, 7] -> Option B

4. Quick Check:

   Pattern found at indices 2 and 7 [OK]

Hint: Look for pattern start indices in text [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Confusing indices starting at 0 or 1
• Misreading pattern occurrences

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

fn compute_lps(pattern: &str) -> Vec<usize> {
    let mut lps = vec![0; pattern.len()];
    let mut length = 0;
    let mut i = 0;
    while i < pattern.len() {
        if pattern.as_bytes()[i] == pattern.as_bytes()[length] {
            length += 1;
            lps[i] = length;
            i += 1;
        } else if length > 0 {
            length = lps[length - 1];
        } else {
            lps[i] = 0;
            i += 1;
        }
    }
    lps
}

medium

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

B. The length variable should be initialized to 1

C. The lps vector should be of type Vec<i32>

D. The function should return a single usize, not a vector

Solution

1. Step 1: Analyze loop initialization

   The prefix table computation starts comparing from the second character, so i must start at 1, not 0.

2. Step 2: Check other variables and return type

   Length starts at 0 correctly, lps vector type usize is correct, and returning a vector is expected.

3. Final Answer:

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

4. Quick Check:

   Start i at 1 for prefix table [OK]

Hint: Prefix table loop starts at second character (i=1) [OK]

Common Mistakes:

• Starting loop at 0 causing incorrect prefix values
• Changing length initialization wrongly
• Wrong return type assumptions

5. Given a text of length 1000 and a pattern of length 10, what is the worst-case time complexity of the KMP algorithm and why?

hard

A. O(n log m) because it uses binary search on the pattern

B. O(n * m) because it checks every character of text with every character of pattern

C. O(n + m) because KMP avoids rechecking characters using the prefix table

D. O(m^2) because prefix table computation is quadratic

Solution

1. Step 1: Understand KMP time complexity

   KMP processes the text and pattern in linear time by using the prefix table to skip unnecessary comparisons.

2. Step 2: Compare with other complexities

   Naive search is O(n*m), binary search is unrelated, and prefix table computation is O(m), not quadratic.

3. Final Answer:

   O(n + m) because KMP avoids rechecking characters using the prefix table -> Option C

4. Quick Check:

   KMP = linear time O(n + m) [OK]

Hint: KMP runs in linear time using prefix table [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing prefix table with binary search
• Thinking prefix table is quadratic