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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of KMP search with overlapping patterns

What is the output of the following Go code that uses KMP to find all occurrences of the pattern in the text?

DSA Go

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 KMPSearch(text, pattern string) []int {
    lps := computeLPS(pattern)
    var result []int
    i, j := 0, 0
    for i < len(text) {
        if text[i] == pattern[j] {
            i++
            j++
        }
        if j == len(pattern) {
            result = append(result, i-j)
            j = lps[j-1]
        } else if i < len(text) && text[i] != pattern[j] {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    return result
}

func main() {
    text := "ababcabcababc"
    pattern := "abcab"
    positions := KMPSearch(text, pattern)
    fmt.Println(positions)
}

A [2 5]

B [5 7]

C [2 5 7]

D [2 7]

💡 Hint

Trace the pattern matching step by step and note where the pattern fully matches in the text.

The pattern "abcab" appears in the text at indices 2 and 5. The KMP algorithm efficiently finds these positions by using the LPS array to skip unnecessary comparisons.

🧠 Conceptual

intermediate

Understanding the LPS array in KMP

What does the LPS (Longest Prefix Suffix) array represent in the KMP algorithm for the pattern "aabaabaaa"?

A The positions where the pattern matches the text

B The count of vowels in the pattern up to each position

C The length of the longest prefix which is also a suffix for each prefix of the pattern

D The number of times the pattern appears in the text

💡 Hint

Think about what helps KMP avoid rechecking characters.

The LPS array stores for each position the length of the longest proper prefix which is also a suffix. This helps the algorithm know where to continue matching after a mismatch.

🔧 Debug

advanced

Identify the error in this KMP implementation snippet

What error will the following Go code snippet produce when computing the LPS array?

DSA Go

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
}

A compilation error: missing return statement

B runtime error: index out of range

C logic error: incorrect LPS values

D no error, runs correctly

💡 Hint

Check the loop condition and indexing carefully.

The loop uses 'i <= len(pattern)', but valid indices go only up to len(pattern)-1. Accessing pattern[i] when i == len(pattern) causes an index out of range runtime error.

❓ Predict Output

advanced

Output of KMP search with no pattern match

What will be the output of the following Go code when searching for pattern "xyz" in text "abcdefgh"?

DSA Go

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 KMPSearch(text, pattern string) []int {
    lps := computeLPS(pattern)
    var result []int
    i, j := 0, 0
    for i < len(text) {
        if text[i] == pattern[j] {
            i++
            j++
        }
        if j == len(pattern) {
            result = append(result, i-j)
            j = lps[j-1]
        } else if i < len(text) && text[i] != pattern[j] {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    return result
}

func main() {
    text := "abcdefgh"
    pattern := "xyz"
    positions := KMPSearch(text, pattern)
    fmt.Println(positions)
}

A [2 4]

B [0]

C [5]

D []

💡 Hint

If the pattern does not appear in the text, what does the result list contain?

Since the pattern "xyz" does not appear in the text "abcdefgh", the result slice remains empty and prints as [].

🧠 Conceptual

expert

Time complexity of KMP algorithm

What is the time complexity of the KMP pattern matching algorithm in terms of text length n and pattern length m?

A O(n + m)

B O(n * m)

C O(n^2)

D O(m^2)

💡 Hint

Consider how many times each character in text and pattern is processed.

KMP processes each character in the text and pattern at most once, resulting in linear time complexity O(n + m).

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