KMP Pattern Matching Algorithm in DSA Go - Deep Dive

Overview - KMP Pattern Matching Algorithm

What is it?

The KMP Pattern Matching Algorithm is a way to find if a smaller string (pattern) appears inside a bigger string (text). It does this efficiently by avoiding repeated checks of characters that are already known to match. Instead of starting over after a mismatch, it uses information from previous matches to skip ahead. This makes searching much faster than checking every position one by one.

Why it matters

Without KMP, searching for patterns in text can be slow, especially with large texts or many searches. This can make tasks like searching documents, DNA sequences, or logs inefficient. KMP speeds up these searches, saving time and computing power, which is important in real-world applications like search engines, text editors, and bioinformatics.

Where it fits

Before learning KMP, you should understand basic string operations and simple pattern searching methods like the naive approach. After KMP, you can explore more advanced string algorithms like Rabin-Karp, Boyer-Moore, and suffix trees for even faster or specialized searches.

Mental Model

Core Idea

KMP uses a precomputed table to remember how far to jump in the pattern after a mismatch, so it never rechecks characters unnecessarily.

Think of it like...

Imagine reading a book and looking for a phrase. If you find a mismatch, instead of going back to the start of the phrase, you remember how much of the phrase you matched and jump to the part where the next match could begin, saving time.

Text:    a b c d a b c d a b c d
Pattern:       a b c d a b

KMP Table (lps): 0 0 0 0 1 2

Matching process:
Text:    a b c d a b c d a b c d
Pattern:       a b c d a b
          ↑ ↑ ↑ ↑ ↑ ↑
When mismatch at position 6, jump pattern index to lps[5]=2 instead of 0.

Build-Up - 6 Steps

1

Foundation

Understanding Basic Pattern Search

Concept: Introduce the naive way to find a pattern in text by checking every position.

To find a pattern in a text, start at the first character of the text and compare it with the first character of the pattern. If they match, check the next characters one by one. If a mismatch happens, move to the next character in the text and start over. Repeat until the pattern is found or the text ends.

Result

This method works but can be slow because it may check the same characters multiple times.

Understanding the naive approach shows why repeated checks waste time and sets the stage for improving search efficiency.

2

Foundation

What is the Longest Prefix Suffix (LPS) Array

Concept: Learn about the LPS array that stores the longest prefix which is also a suffix for each pattern prefix.

The LPS array helps us know how much of the pattern matches itself at different points. For each position in the pattern, LPS tells the length of the longest prefix that matches a suffix ending there. For example, in 'abab', the LPS array is [0,0,1,2]. This means at position 3, the longest prefix-suffix is length 2 ('ab').

Result

The LPS array is ready to guide the search to skip unnecessary comparisons.

Knowing the LPS array is key because it encodes the pattern's internal structure, enabling efficient jumps after mismatches.

3

Intermediate

Building the LPS Array Step-by-Step

🤔Before reading on: do you think the LPS array can be built by comparing the pattern to itself from the start or end? Commit to your answer.

Concept: Learn how to construct the LPS array by comparing characters within the pattern using two pointers.

Start with two pointers: length = 0 (tracks longest prefix suffix) and i = 1 (current position). Compare pattern[i] with pattern[length]. If they match, increment length and set lps[i] = length, then move i forward. If they don't match and length > 0, set length = lps[length-1] and try again. If length is 0, set lps[i] = 0 and move i forward. Repeat until the whole pattern is processed.

Result

The LPS array is built in linear time, capturing the pattern's prefix-suffix info.

Understanding this process reveals how KMP prepares to skip ahead efficiently during search.

4

Intermediate

Using LPS to Search Pattern in Text

🤔Before reading on: do you think KMP restarts matching from the beginning of the pattern after a mismatch? Commit to yes or no.

Concept: Apply the LPS array to avoid restarting from scratch when a mismatch happens during search.

Use two indexes: i for text and j for pattern. Compare text[i] and pattern[j]. If they match, move both forward. If j reaches pattern length, pattern found; record position and set j = lps[j-1] to continue searching. If mismatch and j > 0, set j = lps[j-1] to skip ahead. If j == 0, move i forward. This way, the search never goes backward in text.

Result

Pattern search completes faster by skipping unnecessary comparisons.

Knowing how to use LPS during search is the core of KMP's efficiency advantage.

5

Advanced

Implementing KMP in Go with Comments

🤔Before reading on: do you think the LPS array is computed once or multiple times during search? Commit to your answer.

Concept: See a complete Go code example that builds LPS and searches pattern in text using KMP.

package main import "fmt" // computeLPS builds the longest prefix suffix array for the pattern 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 } // KMPSearch searches for pattern in text and returns starting indices 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 j != 0 { j = lps[j-1] } else { i++ } } } return result } func main() { text := "ababcabcabababd" pattern := "ababd" positions := KMPSearch(text, pattern) fmt.Println(positions) }

Result

[10]

Seeing the full code connects theory to practice and shows how KMP is implemented efficiently in a real language.

6

Expert

Why KMP is Optimal and Its Limitations

🤔Before reading on: do you think KMP always beats other pattern matching algorithms in every scenario? Commit to yes or no.

Concept: Understand KMP's linear time guarantee and when it might not be the best choice.

KMP guarantees O(n) time by never backing up in the text, thanks to the LPS array. However, it requires preprocessing the pattern and works best when patterns are reused or searched multiple times. For very large alphabets or random patterns, other algorithms like Boyer-Moore may perform better due to larger jumps. Also, KMP is less suited for approximate matching or complex patterns.

Result

KMP is a reliable, efficient algorithm but not always the fastest in all contexts.

Knowing KMP's strengths and limits helps choose the right tool for different pattern matching problems.

Under the Hood

KMP works by precomputing the LPS array that encodes how the pattern matches itself. During search, when a mismatch occurs, instead of moving the text pointer back, KMP uses the LPS array to shift the pattern pointer to the longest prefix that matches a suffix, thus skipping redundant comparisons. This avoids re-examining characters in the text, ensuring each character is processed at most once.

Why designed this way?

KMP was designed to improve on the naive search's inefficiency by using pattern self-information. Early string search algorithms restarted matching from scratch after mismatches, wasting time. KMP's innovation was to reuse previous match knowledge, balancing preprocessing cost with faster search. Alternatives like Boyer-Moore came later, focusing on different heuristics for even faster average performance.

Text:  a b a b c a b a b a b d
Pattern:    a b a b d

LPS:    0 0 1 2 0

Matching flow:
[Match a] [Match b] [Match a] [Match b] [Mismatch d]
Pattern index jumps from 4 to LPS[3]=2
Continue matching from pattern[2] without moving text pointer back.

Myth Busters - 3 Common Misconceptions

Quick: Does KMP restart matching from the pattern start after every mismatch? Commit yes or no.

Common Belief: KMP restarts matching from the beginning of the pattern after every mismatch.

Reality: KMP uses the LPS array to jump to a position inside the pattern, not necessarily the start, avoiding repeated checks.

Why it matters: Believing this causes confusion about KMP's efficiency and leads to incorrect implementations that lose its speed advantage.

Quick: Is the LPS array built from the text or the pattern? Commit your answer.

Common Belief: The LPS array is built from the text string.

Reality: The LPS array is built only from the pattern string to capture its internal prefix-suffix structure.

Why it matters: Mixing this up can cause incorrect LPS computation and failed pattern searches.

Quick: Does KMP work well for approximate pattern matching? Commit yes or no.

Common Belief: KMP can be used directly for approximate or fuzzy pattern matching.

Reality: KMP is designed for exact pattern matching only; it does not handle mismatches or errors in the pattern.

Why it matters: Using KMP for approximate matching leads to wrong results; specialized algorithms are needed instead.

Expert Zone

1

The LPS array can be reused for multiple searches of the same pattern, saving preprocessing time in repeated queries.

2

KMP's linear time guarantee holds even in worst-case inputs where naive search degrades to quadratic time.

3

The algorithm's efficiency depends on the pattern's structure; highly repetitive patterns produce longer LPS values, enabling bigger jumps.

When NOT to use

Avoid KMP when searching for approximate matches or patterns with wildcards; use algorithms like the Levenshtein automaton or Bitap instead. For very large alphabets or when average-case speed matters more than worst-case, consider Boyer-Moore or Rabin-Karp algorithms.

Production Patterns

KMP is used in text editors for fast find operations, in bioinformatics for DNA sequence matching, and in network security for pattern detection in data streams. Its predictable linear time makes it suitable for real-time systems where worst-case performance matters.

Connections

Finite Automata

KMP's LPS array can be seen as a simplified finite automaton that guides pattern matching states.

Understanding KMP as a state machine helps grasp how pattern matching progresses without backtracking.

Dynamic Programming

Building the LPS array uses overlapping subproblems similar to dynamic programming techniques.

Recognizing this connection clarifies why LPS computation is efficient and avoids redundant work.

Human Memory and Pattern Recognition

KMP mimics how humans remember partial matches to avoid rechecking from scratch when searching for patterns.

This cross-domain link shows how algorithms can reflect cognitive strategies for efficient problem solving.

Common Pitfalls

#1 Incorrectly resetting the pattern index to zero after mismatch instead of using LPS.

Wrong approach:

if mismatch {
j = 0 // wrong: resets pattern index
}

Correct approach:

if mismatch {
if j != 0 {
j = lps[j-1]
} else {
i++
}
}

Root cause:

Misunderstanding the purpose of the LPS array and treating KMP like naive search.

#2 Building LPS array by comparing pattern characters only once without backtracking length pointer.

Wrong approach:

for i := 1; i < len(pattern); i++ {
if pattern[i] == pattern[i-1] {
lps[i] = lps[i-1] + 1
} else {
lps[i] = 0
}
}

Correct approach:

Use two pointers i and length, and update length using lps[length-1] when mismatch occurs during LPS computation.

Root cause:

Oversimplifying LPS computation and ignoring the need to backtrack length pointer.

#3 Using KMP for approximate matching expecting it to handle errors.

Wrong approach:

positions := KMPSearch(text, patternWithTypos)

Correct approach:

Use specialized approximate matching algorithms like Bitap or dynamic programming based methods.

Root cause:

Confusing exact pattern matching algorithms with approximate matching needs.

Key Takeaways

KMP improves pattern searching by using a precomputed LPS array to skip unnecessary comparisons after mismatches.

The LPS array captures the longest prefix-suffix information of the pattern, enabling efficient jumps during search.

KMP guarantees linear time complexity, making it reliable for large texts and worst-case inputs.

Understanding how to build and use the LPS array is essential to implementing KMP correctly.

KMP is best for exact matching and repeated searches but has limits compared to other algorithms for approximate or complex patterns.

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