Why KMP Pattern Matching Algorithm in DSA Python?

The Big Idea

What if you could find a phrase in a huge book without ever rereading the same page twice?

The Scenario

Imagine you have a huge book and you want to find every place where a certain phrase appears. You start reading from the beginning each time you find a mismatch, going back and forth repeatedly.

The Problem

This manual search is very slow because you waste time rechecking letters you already know don't match. It's like reading the same pages over and over, which is tiring and frustrating.

The Solution

The KMP algorithm cleverly remembers where to restart the search without going back to the start. It uses a helper table to skip unnecessary checks, making the search much faster and smoother.

Before vs After

✗ Before

def search(text, pattern):
    for i in range(len(text) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and text[i + j] == pattern[j]:
            j += 1
        if j == len(pattern):
            print('Found at', i)

✓ After

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                print('Found at', i - j)
                j = lps[j - 1]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

What It Enables

KMP enables lightning-fast pattern searches in large texts without wasting time on repeated checks.

Real Life Example

Search engines use KMP-like algorithms to quickly find your search words inside billions of web pages instantly.

Key Takeaways

Manual search repeats checks and is slow.

KMP uses a helper table to skip unnecessary comparisons.

This makes pattern searching efficient and fast.

Practice

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

easy

A. To calculate the factorial of a number recursively

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To find occurrences of a pattern string within a text efficiently

Solution

1. Step 1: Understand the goal of KMP algorithm

   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 D

4. Quick Check:

   KMP = Pattern search [OK]

Hint: KMP is about fast pattern search 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 initialize the prefix table (lps array) in KMP algorithm in Python?

easy

A. lps = [0] * len(pattern)

B. lps = []

C. lps = [1] * len(pattern)

D. lps = None

Solution

1. Step 1: Understand the prefix table initialization

   The prefix table (lps array) stores lengths of longest proper prefix which is also suffix for each prefix of the pattern. It must be initialized with zeros for all positions.

2. Step 2: Check each option

   lps = [0] * len(pattern) correctly initializes lps with zeros for the entire pattern length. lps = [] is empty list, which is incomplete. lps = [1] * len(pattern) initializes with ones, which is incorrect. lps = None sets None, which is invalid.

3. Final Answer:

   lps = [0] * len(pattern) -> Option A

4. Quick Check:

   Prefix table starts with zeros [OK]

Hint: Prefix table starts with zeros for all pattern chars [OK]

Common Mistakes:

• Initializing lps with ones instead of zeros
• Leaving lps empty
• Assigning None to lps

3. What will be the output of the following Python code snippet using KMP algorithm?

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

pattern = "ABABC"
lps = compute_lps(pattern)
print(lps)

medium

A. [1, 0, 1, 0, 1]

B. [0, 0, 1, 2, 0]

C. [0, 1, 2, 3, 4]

D. [0, 0, 0, 0, 0]

Solution

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

   Index 0: lps[0] = 0 (always zero)
   Index 1: pattern[1] = 'B' != pattern[0] = 'A', lps[1] = 0
   Index 2: pattern[2] = 'A' == pattern[0] = 'A', lps[2] = 1
   Index 3: pattern[3] = 'B' == pattern[1] = 'B', lps[3] = 2
   Index 4: pattern[4] = 'C' != pattern[2] = 'A', lps[4] = 0

2. Step 2: Final lps array

   The computed lps array is [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option B

4. Quick Check:

   lps for "ABABC" = [0,0,1,2,0] [OK]

Hint: Match prefix and suffix lengths stepwise [OK]

Common Mistakes:

• Confusing lps values with pattern indices
• Assuming all zeros or all increasing values
• Mixing up characters when comparing

4. Identify the error in the following KMP prefix table computation code snippet:

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 0
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

medium

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

B. The lps array should be initialized with ones

C. The length variable should start at 1

D. The function should return pattern instead of lps

Solution

1. Step 1: Analyze the loop initialization

   In KMP prefix table computation, the first character's lps is always zero and we start comparing from the second character, so i should start at 1.

2. Step 2: Check the given code

   The code starts with i = 0, which causes comparing pattern[0] with pattern[0] immediately, leading to incorrect lps values and infinite loop risk.

3. Final Answer:

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

4. Quick Check:

   Start i at 1 for prefix table [OK]

Hint: Start prefix loop from second character (i=1) [OK]

Common Mistakes:

• Starting loop at zero causing wrong comparisons
• Initializing lps with ones instead of zeros
• Returning wrong variable

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

hard

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the pattern and text

   The pattern "ABABCABAB" is searched inside the text "ABABDABACDABABCABAB" using KMP which efficiently finds all occurrences.

2. Step 2: Identify pattern occurrences

   By scanning the text:
   - Occurrence starts at index 10 (substring "ABABCABAB")
   So pattern appears 1 time.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Pattern appears once in text [OK]

Hint: Count all pattern matches including overlaps [OK]

Common Mistakes:

• Counting only first occurrence
• Ignoring overlapping matches
• Misreading pattern or text