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

Recall & Review

beginner

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

KMP (Knuth-Morris-Pratt) algorithm is used to find occurrences of a "pattern" string inside a "text" string efficiently without rechecking characters unnecessarily.

intermediate

What is the 'lps' array in KMP algorithm?

The 'lps' (Longest Prefix Suffix) 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 characters while matching.

intermediate

How does KMP avoid rechecking characters in the text?

KMP uses the 'lps' array to know how many characters can be skipped after a mismatch, so it doesn't start matching from the beginning of the pattern again.

intermediate

What is the time complexity of the KMP algorithm?

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

intermediate

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

When a mismatch occurs, KMP uses the 'lps' array to shift the pattern to the right position without moving back in the text, continuing the search efficiently.

What does the 'lps' array represent in KMP?

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 suffix for each prefix of the pattern.

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

A It skips unnecessary comparisons using the lps array

B It uses recursion to find matches

C It sorts the text before searching

D It uses hashing to find matches

KMP uses the lps array to skip characters and avoid rechecking, making it more efficient than naive search.

What is the worst-case time complexity of KMP?

A O(n^2)

B O(n * m)

C O(n + m)

D O(m^2)

KMP runs in linear time relative to the sum of text and pattern lengths, O(n + m).

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

A Moves the pattern completely past the mismatch

B Moves the text pointer back

C Restarts matching from the beginning of the text

D Uses the lps array to shift the pattern without moving text pointer back

KMP uses the lps array to shift the pattern smartly without moving the text pointer back.

Which of these is NOT a step in KMP algorithm?

A Preprocessing pattern to build lps array

B Sorting the text before searching

C Comparing characters of text and pattern

D Using lps array to skip characters after mismatch

KMP does not sort the text; it uses pattern preprocessing and smart skipping.

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

Think about longest prefix which is also suffix and how it avoids rechecking.

Describe the step-by-step process of searching a pattern in text using the KMP algorithm.

Start from building lps, then matching, then what happens on mismatch.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) algorithm in pattern matching?

easy

A. To efficiently find occurrences of a pattern in a text without rechecking characters

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the number of vowels in the text

Solution

1. Step 1: Understand KMP's goal

   KMP is designed to find pattern matches in text efficiently by avoiding repeated comparisons.

2. Step 2: Compare options with KMP's function

   Only To efficiently find occurrences of a pattern in a text without rechecking characters describes this efficient search without rechecking characters.

3. Final Answer:

   To efficiently find occurrences of a pattern in a text without rechecking characters -> Option A

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP avoids rechecking characters during pattern search [OK]

Common Mistakes:

• Thinking KMP sorts or modifies the text
• Confusing KMP with simple substring search
• Assuming KMP counts characters instead of searching

2. Which of the following is the correct way to declare the prefix table (lps array) in Go for KMP algorithm?

easy

A. lps := []string{len(pattern)}

B. lps := make([]int, len(pattern))

C. lps := make([]bool, len(pattern))

D. lps := new(int)

Solution

1. Step 1: Identify correct Go syntax for integer slice

   In Go, make([]int, size) creates an integer slice of given size.

2. Step 2: Check options for correct slice creation

   lps := make([]int, len(pattern)) correctly creates an int slice for lps. Others use wrong types or syntax.

3. Final Answer:

   lps := make([]int, len(pattern)) -> Option B

4. Quick Check:

   Go slice for lps = make([]int, len(pattern)) [OK]

Hint: Use make([]int, size) to create integer slices in Go [OK]

Common Mistakes:

• Using wrong slice type like []string or []bool
• Using new(int) which creates a pointer, not slice
• Incorrect slice initialization syntax

3. What will be the output of the following Go code snippet that uses KMP to find pattern occurrences?

package main
import "fmt"

func computeLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

func main() {
    pattern := "ABABC"
    lps := computeLPS(pattern)
    fmt.Println(lps)
}

medium

A. [0 0 0 0 0]

B. [0 1 2 3 4]

C. [1 2 3 4 5]

D. [0 0 1 2 0]

Solution

1. Step 1: Compute LPS array for pattern "ABABC"

   Check characters stepwise: - i=1: 'B' != 'A' => lps[1]=0 - i=2: 'A' == 'A' => length=1, lps[2]=1 - i=3: 'B' == 'B' => length=2, lps[3]=2 - i=4: 'C' != 'A' => length=lps[1]=0, lps[4]=0

2. Step 2: Final LPS array is [0, 0, 1, 2, 0]

   This matches [0 0 1 2 0] exactly.

3. Final Answer:

   [0 0 1 2 0] -> Option D

4. Quick Check:

   LPS for "ABABC" = [0 0 1 2 0] [OK]

Hint: Trace pattern chars to build LPS stepwise [OK]

Common Mistakes:

• Confusing LPS values with pattern indices
• Not resetting length correctly on mismatch
• Assuming all zeros or increasing sequence

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

func computeLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 0
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

medium

A. The function should return a string, not []int

B. The length variable should be initialized to 1

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

D. The lps array should be of type []bool

Solution

1. Step 1: Check loop initialization for LPS computation

   In KMP, i starts from 1 because lps[0] is always 0 and no comparison needed at index 0.

2. Step 2: Identify incorrect i initialization

   Here i starts at 0, causing incorrect comparisons and possible infinite loop.

3. Final Answer:

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

4. Quick Check:

   Start i=1 for LPS loop [OK]

Hint: LPS loop always starts at index 1 [OK]

Common Mistakes:

• Starting loop at 0 causing wrong LPS values
• Initializing length incorrectly
• Wrong return type or array type

5. Given the text "ABABDABACDABABCABAB" and pattern "ABABCABAB", how many times does the pattern occur in the text using KMP algorithm?

hard

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Understand the pattern and text

   The pattern "ABABCABAB" appears in the text at indices 10 and 12 (0-based indexing), overlapping occurrences.

2. Step 2: Count occurrences using KMP logic

   KMP finds two matches without rechecking characters, so total occurrences = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pattern occurs twice in text [OK]

Hint: Use KMP to find all pattern matches efficiently [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Overcounting occurrences
• Assuming zero matches due to complexity