KMP Pattern Matching Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of KMP prefix table computation

What is the output of the prefix table (lps array) after running the KMP preprocessing on the pattern "ABABC"?

DSA Rust

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

fn main() {
    let pattern = "ABABC";
    let lps = compute_lps(pattern);
    println!("{:?}", lps);
}

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

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

C [0, 0, 1, 2, 0]

D [1, 0, 1, 2, 0]

💡 Hint

Remember the prefix table stores the length of the longest proper prefix which is also a suffix for each substring.

The prefix table for "ABABC" is computed as follows: positions 0 and 1 have 0 because no proper prefix matches suffix; at position 2, 'A' matches start, so 1; at position 3, 'B' matches next, so 2; at position 4, no match, so 0.

❓ Predict Output

intermediate

KMP search result index

What is the output index when searching for pattern "ABCDABD" in text "ABC ABCDAB ABCDABCDABDE" using KMP algorithm?

DSA Rust

fn kmp_search(text: &str, pattern: &str) -> Option<usize> {
    let lps = compute_lps(pattern);
    let text_chars: Vec<char> = text.chars().collect();
    let pattern_chars: Vec<char> = pattern.chars().collect();
    let mut i = 0;
    let mut j = 0;
    while i < text.len() {
        if text_chars[i] == pattern_chars[j] {
            i += 1;
            j += 1;
            if j == pattern.len() {
                return Some(i - j);
            }
        } else {
            if j != 0 {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }
    None
}

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

fn main() {
    let text = "ABC ABCDAB ABCDABCDABDE";
    let pattern = "ABCDABD";
    match kmp_search(text, pattern) {
        Some(index) => println!("{}", index),
        None => println!("-1"),
    }
}

A 10

B 15

C -1

D 20

💡 Hint

The pattern appears starting at index 15 in the text.

The pattern "ABCDABD" first fully matches starting at index 15 in the given text.

🔧 Debug

advanced

Identify the error in KMP prefix table code

What error will the following Rust code produce when computing the prefix table for pattern "AAAAB"?

DSA Rust

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

fn main() {
    let pattern = "AAAAB";
    let lps = compute_lps(pattern);
    println!("{:?}", lps);
}

A Index out of bounds panic at runtime

B Compilation error: mismatched types

C Infinite loop without termination

D Correct output: [0, 1, 2, 3, 0]

💡 Hint

Check the loop condition and indexing inside the loop.

The loop condition uses <= pattern.len(), which causes index i to reach pattern.len(), leading to out of bounds access on chars[i].

🧠 Conceptual

advanced

Understanding KMP algorithm time complexity

What is the time complexity of the KMP pattern matching algorithm for searching a pattern of length m in a text of length n?

A O(n + m)

B O(m * n)

C O(n * log m)

D O(n^2)

💡 Hint

KMP avoids re-examining characters in the text.

KMP preprocesses the pattern in O(m) and searches in O(n), so total time is O(n + m).

🚀 Application

expert

Find all occurrences of pattern using KMP

Given the text "ABABDABACDABABCABAB" and pattern "ABABCABAB", which option correctly lists all starting indices where the pattern occurs using KMP?

DSA Rust

fn kmp_search_all(text: &str, pattern: &str) -> Vec<usize> {
    let lps = compute_lps(pattern);
    let text_chars: Vec<char> = text.chars().collect();
    let pattern_chars: Vec<char> = pattern.chars().collect();
    let mut i = 0;
    let mut j = 0;
    let mut result = Vec::new();
    while i < text.len() {
        if text_chars[i] == pattern_chars[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;
    let chars: Vec<char> = pattern.chars().collect();
    while i < pattern.len() {
        if chars[i] == chars[length] {
            length += 1;
            lps[i] = length;
            i += 1;
        } else {
            if length != 0 {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i += 1;
            }
        }
    }
    lps
}

fn main() {
    let text = "ABABDABACDABABCABAB";
    let pattern = "ABABCABAB";
    let occurrences = kmp_search_all(text, pattern);
    println!("{:?}", occurrences);
}

A []

B [10, 15]

C [0, 10]

D [10]

💡 Hint

The pattern appears once starting at index 10.

The pattern "ABABCABAB" occurs only once in the text starting at index 10.

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