KMP Pattern Matching Algorithm in DSA Python - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: You are building a simple text search tool that finds all positions where a small pattern appears inside a larger text. This is useful in searching documents, DNA sequences, or logs quickly.

🎯 Goal: Implement the Knuth-Morris-Pratt (KMP) algorithm to efficiently find all starting indexes of a pattern inside a given text.

📋 What You'll Learn

Create a list called lps to store longest prefix suffix values for the pattern

Create a function compute_lps(pattern) to fill the lps list

Create a function kmp_search(text, pattern) that uses lps to find all pattern matches in the text

Print the list of starting indexes where the pattern is found in the text

💡 Why This Matters

🌍 Real World

Text search is used in search engines, DNA sequence analysis, plagiarism detection, and log file analysis.

💼 Career

Understanding KMP algorithm helps in roles involving software development, data processing, and algorithm optimization.

1

Create the text and pattern variables

Create a variable called text and set it to the string 'ABABDABACDABABCABAB'. Create a variable called pattern and set it to the string 'ABABCABAB'.

DSA Python

# Create variables text and pattern with given strings
# Your code here

Hint

Use simple string assignment for both text and pattern.

2

Create the LPS array and the compute_lps function

Create a list called lps with length equal to len(pattern) filled with zeros. Define a function called compute_lps(pattern) that fills the lps list with longest prefix suffix values for the given pattern. Use variables length and i inside the function to track prefix length and current index.

DSA Python

text = 'ABABDABACDABABCABAB'
pattern = 'ABABCABAB'
# Create lps list and compute_lps function
# Your code here

Hint

The lps list stores the length of the longest proper prefix which is also a suffix for each prefix of the pattern.

3

Create the kmp_search function to find pattern matches

Define a function called kmp_search(text, pattern) that uses the lps list to find all starting indexes where pattern appears in text. Use variables i for text index and j for pattern index. Return a list called result containing all matching start indexes.

DSA Python

text = 'ABABDABACDABABCABAB'
pattern = 'ABABCABAB'
lps = [0] * len(pattern)

def compute_lps(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

# Define kmp_search function to find all pattern matches
# Your code here

Hint

Use two pointers to scan the text and pattern. When characters match, move both pointers. When mismatch occurs, use lps to avoid rechecking characters.

4

Print the list of pattern match starting indexes

Call the function kmp_search(text, pattern) and print the returned list of starting indexes where the pattern is found in the text.

DSA Python

text = 'ABABDABACDABABCABAB'
pattern = 'ABABCABAB'
lps = [0] * len(pattern)

def compute_lps(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

def kmp_search(text, pattern):
    compute_lps(pattern)
    result = []
    i = 0
    j = 0
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            result.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return result

# Print the list of pattern match starting indexes
# Your code here

Hint

The pattern appears starting at index 10 in the text. Printing the result list shows [10].

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