KMP Pattern Matching Algorithm in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does KMP stand for in the KMP Pattern Matching Algorithm?

KMP stands for Knuth-Morris-Pratt, named after the three computer scientists who developed the algorithm.

beginner

What is the main advantage of the KMP algorithm over the naive pattern matching approach?

KMP avoids rechecking characters that have already been matched by using a precomputed prefix table, making it faster especially for large texts and patterns.

intermediate

What is the purpose of the 'lps' (Longest Prefix Suffix) array in KMP?

The 'lps' array stores the length of the longest proper prefix of the pattern that is also a suffix for each prefix of the pattern. It helps to skip unnecessary comparisons.

intermediate

In KMP, what happens when a mismatch occurs after some matches?

Instead of restarting from the next character in the text, KMP uses the 'lps' array to shift the pattern to the right position, avoiding rechecking matched characters.

intermediate

What is the time complexity of the KMP Pattern Matching Algorithm?

The time complexity is O(n + m), where n is the length of the text and m is the length of the pattern, because each character is processed at most twice.

What does the 'lps' array represent in the KMP algorithm?

A Longest prefix which is also suffix for pattern prefixes

B Length of the pattern

C Positions of matches in the text

D Number of mismatches found

The 'lps' array stores the longest proper prefix which is also a suffix for each prefix of the pattern.

What is the main benefit of using KMP over naive pattern matching?

A It uses less memory

B It finds all substrings in constant time

C It works only on sorted text

D It avoids rechecking matched characters after mismatch

KMP avoids rechecking characters that have already been matched by using the 'lps' array.

If the pattern is 'ABABC', what is the lps value for the last character 'C'?

A 0

B 1

C 2

D 3

For 'ABABC', the longest prefix which is also suffix for the full pattern is 0 because no proper prefix matches suffix ending at 'C'.

What is the worst-case time complexity of KMP algorithm?

A O(n*m)

B O(n + m)

C O(n^2)

D O(m^2)

KMP runs in linear time O(n + m), where n is text length and m is pattern length.

When a mismatch occurs in KMP, what does the algorithm do next?

A Restart matching from the next character in text

B Stop searching

C Shift pattern using lps array to avoid rechecking

D Reverse the pattern

KMP uses the lps array to shift the pattern smartly to avoid rechecking matched characters.

Explain how the 'lps' array is constructed in the KMP algorithm and why it is important.

Think about how pattern prefixes relate to suffixes and how this helps avoid repeated work.

Describe the process of pattern matching in KMP when a mismatch occurs after some characters have matched.

Focus on how KMP uses previous knowledge to skip unnecessary checks.

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