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].