KMP Pattern Matching Algorithm in DSA Rust - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: Imagine you are building a text search tool that quickly finds a smaller word or phrase inside a large document. This tool uses a smart method called the KMP algorithm to avoid checking the same letters again and again.

🎯 Goal: You will build the KMP pattern matching algorithm in Rust step-by-step. This algorithm helps find all places where a pattern appears inside a text efficiently.

📋 What You'll Learn

Create a function to build the longest prefix suffix (LPS) array for the pattern

Create a function to use the LPS array to find all pattern matches in the text

Print the starting indexes of all matches found

💡 Why This Matters

🌍 Real World

Text editors, search engines, and DNA sequence analysis use pattern matching algorithms like KMP to quickly find patterns in large data.

💼 Career

Understanding KMP helps in roles involving text processing, software development, and algorithm optimization.

1

Create the pattern and text variables

Create a variable called pattern with the value "ABABCABAB" and a variable called text with the value "ABABDABACDABABCABAB".

DSA Rust

# Create the pattern and text variables
# Your code here

Hint

Use let to create variables for pattern and text with the exact strings given.

2

Build the longest prefix suffix (LPS) array

Create a function called build_lps that takes a &str called pattern and returns a Vec. Inside it, create a mutable vector lps of length pattern.len() filled with zeros. Use variables length set to 0 and i set to 1. Use a while loop with condition i < pattern.len() to fill the lps array following the KMP logic. Return lps at the end.

DSA Rust

fn main() {
    let pattern = "ABABCABAB";
    let text = "ABABDABACDABABCABAB";
}

// Create the build_lps function here
// Your code here

Hint

Remember to compare characters using bytes and update length and lps according to the KMP prefix logic.

3

Implement the KMP search function

Create a function called kmp_search that takes text: &str and pattern: &str and returns a Vec of starting indexes where the pattern is found. Inside, call build_lps(pattern) to get the lps array. Use variables i and j set to 0 to track positions in text and pattern. Use a while loop with condition i < text.len() to compare characters and find matches using the KMP logic. Collect all match start indexes in a vector called result and return it.

DSA Rust

fn build_lps(pattern: &str) -> Vec {
    // existing code
}

// Create the kmp_search function here
// Your code here

fn main() {
    let pattern = "ABABCABAB";
    let text = "ABABDABACDABABCABAB";
}

Hint

Use two indexes i and j to scan text and pattern. Use the lps array to skip characters when mismatch happens.

4

Print all pattern match positions

Call the kmp_search function with text and pattern variables. Store the result in a variable called matches. Print the matches vector.

DSA Rust

fn build_lps(pattern: &str) -> Vec {
    // existing code
}

fn kmp_search(text: &str, pattern: &str) -> Vec {
    // existing code
}

fn main() {
    let pattern = "ABABCABAB";
    let text = "ABABDABACDABABCABAB";

    // Call kmp_search and print matches here
    // Your code here
}

Hint

The pattern appears starting at index 10 in the text. Print the vector of matches using println!("{:?}", matches);.

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