KMP Pattern Matching Algorithm in DSA Rust

Mental Model

KMP finds a pattern in a text by skipping unnecessary checks using a precomputed table.

Analogy: Like searching a word in a book by remembering how much of the word matched before, so you don't start over from the first letter every time.

Text:  A B C D A B C D A B C D
Pattern:       A B C D
Prefix Table: [0,0,0,0]

Dry Run Walkthrough

Input: text: "ABABDABACDABABCABAB", pattern: "ABABCABAB"

Goal: Find all starting indices where the pattern appears in the text.

Step 1: Build prefix table for pattern

Pattern: A B A B C A B A B
Prefix Table: [0,0,1,2,0,1,2,3,4]

Why: Prefix table helps to know how many characters to skip after mismatch.

Step 2: Start matching pattern in text from index 0

Text: [A] B A B D A B A C D A B A B C A B A B
Pattern: A B A B C A B A B

Why: Begin comparing pattern with text from start.

Step 3: Match characters until mismatch at text index 4

Matched: A B A B
Mismatch at text[4] = D vs pattern[4] = C

Why: Mismatch found, use prefix table to skip.

Step 4: Use prefix table to shift pattern index from 4 to 0

Pattern index reset to 0, text index stays at 4

Why: Prefix table says no proper prefix, restart pattern matching.

Step 5: Continue matching from text index 5

Text: A B A B D [A] B A C D A B A B C A B A B
Pattern: A B A B C A B A B

Why: Try matching pattern starting at next text character.

Step 6: Find full pattern match starting at text index 10

Match found at text indices 10 to 18

Why: Pattern fully matched in text.

Result:

Match found at index 10

Annotated Code

DSA Rust

struct KMP {
    pattern: Vec<char>,
    prefix_table: Vec<usize>,
}

impl KMP {
    fn new(pattern: &str) -> Self {
        let pattern_chars: Vec<char> = pattern.chars().collect();
        let prefix_table = KMP::build_prefix_table(&pattern_chars);
        KMP { pattern: pattern_chars, prefix_table }
    }

    fn build_prefix_table(pattern: &[char]) -> Vec<usize> {
        let mut prefix_table = vec![0; pattern.len()];
        let mut j = 0;
        for i in 1..pattern.len() {
            while j > 0 && pattern[i] != pattern[j] {
                j = prefix_table[j - 1];
            }
            if pattern[i] == pattern[j] {
                j += 1;
            }
            prefix_table[i] = j;
        }
        prefix_table
    }

    fn search(&self, text: &str) -> Vec<usize> {
        let text_chars: Vec<char> = text.chars().collect();
        let mut result = Vec::new();
        let mut j = 0;
        for i in 0..text_chars.len() {
            while j > 0 && text_chars[i] != self.pattern[j] {
                j = self.prefix_table[j - 1];
            }
            if text_chars[i] == self.pattern[j] {
                j += 1;
            }
            if j == self.pattern.len() {
                result.push(i + 1 - j);
                j = self.prefix_table[j - 1];
            }
        }
        result
    }
}

fn main() {
    let text = "ABABDABACDABABCABAB";
    let pattern = "ABABCABAB";
    let kmp = KMP::new(pattern);
    let matches = kmp.search(text);
    for index in matches {
        println!("Match found at index {}", index);
    }
}

while j > 0 && pattern[i] != pattern[j] { j = prefix_table[j - 1]; }

Backtrack prefix index on mismatch to find longest prefix suffix

if pattern[i] == pattern[j] { j += 1; }

Advance prefix index when characters match

prefix_table[i] = j;

Store length of longest prefix suffix for current position

while j > 0 && text_chars[i] != self.pattern[j] { j = self.prefix_table[j - 1]; }

Backtrack pattern index on mismatch in text

if text_chars[i] == self.pattern[j] { j += 1; }

Advance pattern index on match

if j == self.pattern.len() { result.push(i + 1 - j); j = self.prefix_table[j - 1]; }

Pattern found, record index and reset pattern index for next search

Output

Match found at index 10

Complexity Analysis

Time: O(n + m) because building prefix table takes O(m) and searching takes O(n), where n is text length and m is pattern length

Space: O(m) for prefix table and pattern storage

vs Alternative: Naive search is O(n*m) because it restarts matching from scratch after mismatch; KMP skips unnecessary comparisons using prefix table

Edge Cases

Empty pattern

Returns no matches immediately

DSA Rust

if j == self.pattern.len() { ... }

Pattern longer than text

No matches found, search ends quickly

DSA Rust

for i in 0..text_chars.len() { ... }

Pattern with repeated characters

Prefix table correctly handles repeated prefixes to skip checks

DSA Rust

while j > 0 && pattern[i] != pattern[j] { j = prefix_table[j - 1]; }

When to Use This Pattern

When you need to find a pattern inside a text efficiently and want to avoid rechecking characters after mismatch, use KMP because it uses a prefix table to skip unnecessary comparisons.

Common Mistakes

Mistake: Not updating the pattern index j after a mismatch using the prefix table
Fix: Use the prefix table to reset j to prefix_table[j - 1] inside the while loop on mismatch

Mistake: Building prefix table incorrectly by not handling backtracking properly
Fix: Use a while loop to backtrack j until a match or zero is found when building prefix table

Summary

KMP finds all occurrences of a pattern in a text efficiently by using a prefix table to skip redundant checks.

Use KMP when you need fast pattern searching in large texts without restarting from scratch after mismatches.

The key insight is the prefix table that remembers how much of the pattern matched so far to avoid rechecking characters.

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