KMP Pattern Matching Algorithm in DSA Go

Mental Model

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

Analogy: Imagine searching a word in a book but remembering how much you matched before so you don't start over from the beginning each time.

Text:  A B C D A B C D A B C D
Pattern:      A B C D A B
          ↑
Prefix Table: [0 0 0 0 1 2]

Dry Run Walkthrough

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

Goal: Find the starting index of the pattern in the text using KMP algorithm

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 with 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]
Match indices: text 0-8, pattern 0-8

Why: We compare characters one by one to find full match

Step 3: Mismatch at text index 4 (D) and pattern index 4 (C), use prefix table to shift pattern

Shift pattern to align pattern index 0 with text index 4 (using prefix table value 0)

Why: Prefix table tells how far to jump to avoid rechecking matched chars

Step 4: Continue matching from text index 4 and pattern 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]
Match indices: text 4-12, pattern 0-8

Why: Resume matching after shifting pattern

Step 5: Full pattern matched at text index 10 to 18

Match found starting at index 10 in text

Why: All pattern characters matched in sequence

Result:

Match found at index 10

Annotated Code

DSA Go

package main

import "fmt"

func buildPrefixTable(pattern string) []int {
    prefix := make([]int, len(pattern))
    j := 0
    for i := 1; i < len(pattern); i++ {
        for j > 0 && pattern[i] != pattern[j] {
            j = prefix[j-1] // fallback in prefix table
        }
        if pattern[i] == pattern[j] {
            j++
            prefix[i] = j
        }
    }
    return prefix
}

func kmpSearch(text, pattern string) int {
    if len(pattern) == 0 {
        return 0
    }
    prefix := buildPrefixTable(pattern)
    j := 0
    for i := 0; i < len(text); i++ {
        for j > 0 && text[i] != pattern[j] {
            j = prefix[j-1] // fallback on mismatch
        }
        if text[i] == pattern[j] {
            j++
        }
        if j == len(pattern) {
            return i - j + 1 // match found
        }
    }
    return -1 // no match
}

func main() {
    text := "ABABDABACDABABCABAB"
    pattern := "ABABCABAB"
    index := kmpSearch(text, pattern)
    if index != -1 {
        fmt.Printf("Match found at index %d\n", index)
    } else {
        fmt.Println("No match found")
    }
}

j = prefix[j-1] // fallback in prefix table

fallback to previous longest prefix on mismatch while building prefix table

prefix[i] = j

store length of longest prefix suffix for current position

j = prefix[j-1] // fallback on mismatch

fallback to previous longest prefix on mismatch during search

j++

advance pattern index on character match

return i - j + 1 // match found

return starting index of pattern match in text

Output

Match found at index 10

Complexity Analysis

Time: O(n + m) because we build prefix table in O(m) and search text in O(n) without backtracking

Space: O(m) for prefix table storage where m is pattern length

vs Alternative: Naive search is O(n*m) because it restarts matching from next text index on mismatch

Edge Cases

empty pattern

returns 0 immediately as empty pattern matches at start

DSA Go

if len(pattern) == 0 {
        return 0
    }

pattern longer than text

returns -1 as no match possible

DSA Go

return -1 // no match

pattern not in text

returns -1 after full scan

DSA Go

return -1 // no match

When to Use This Pattern

When you need to find a substring 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 correctly on mismatch using prefix table
Fix: Use j = prefix[j-1] inside the mismatch while loop to fallback properly

Mistake: Forgetting to handle empty pattern case
Fix: Add a guard to return 0 if pattern length is zero

Summary

Finds pattern in text efficiently by precomputing a prefix table to skip redundant checks.

Use when you want fast substring search without restarting from scratch on mismatch.

The key insight is using the prefix table to remember how much of the pattern matched so far.

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