KMP Pattern Matching Algorithm in DSA Python

Mental Model

KMP finds a pattern in text by remembering where to restart after a mismatch, so it never rechecks characters unnecessarily.

Analogy: Imagine searching a word in a book. Instead of starting over after a mismatch, you use a bookmark that tells you where to continue, saving time.

Text:  A B C D A B C D A B C
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 all starting indices where the pattern appears in the text efficiently.

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 know how far to jump back on mismatch.

Step 2: Start matching pattern with text from index 0

Text: A B A B D A B A C D ...
Pattern: A B A B C A B A B
Match indices: 0 to 3 matched

Why: Match characters until mismatch or full pattern matched.

Step 3: Mismatch at text index 4, pattern index 4; use prefix table to shift pattern

Pattern index moves from 4 to prefix_table[3]=2
Text index stays at 4

Why: Avoid rechecking matched characters by jumping pattern index.

Step 4: Continue matching from pattern index 2 and text index 4

Further mismatches occur, matching resumes later from text index 5

Why: Resume matching from shifted pattern position.

Step 5: Full pattern matched at text index 10

Pattern found starting at index 10 in text

Why: We found one occurrence of the pattern.

Step 6: Continue searching for next matches after index 10

j reset to 4, but end of text reached; no more matches

Why: KMP continues to find all occurrences efficiently.

Result:

Pattern found at indices: 10

Annotated Code

DSA Python

class KMPMatcher:
    def __init__(self, pattern: str):
        self.pattern = pattern
        self.prefix_table = self.build_prefix_table(pattern)

    def build_prefix_table(self, pattern: str) -> list[int]:
        prefix = [0] * len(pattern)
        j = 0
        for i in range(1, len(pattern)):
            while j > 0 and pattern[i] != pattern[j]:
                j = prefix[j - 1]  # fallback in prefix table
            if pattern[i] == pattern[j]:
                j += 1
                prefix[i] = j
        return prefix

    def search(self, text: str) -> list[int]:
        result = []
        j = 0  # index for pattern
        for i in range(len(text)):
            while j > 0 and text[i] != self.pattern[j]:
                j = self.prefix_table[j - 1]  # fallback on mismatch
            if text[i] == self.pattern[j]:
                j += 1
            if j == len(self.pattern):
                result.append(i - j + 1)  # match found
                j = self.prefix_table[j - 1]  # continue searching
        return result


if __name__ == '__main__':
    text = 'ABABDABACDABABCABAB'
    pattern = 'ABABCABAB'
    matcher = KMPMatcher(pattern)
    matches = matcher.search(text)
    print('Pattern found at indices:', ', '.join(map(str, matches)))

while j > 0 and pattern[i] != pattern[j]: j = prefix[j - 1] # fallback in prefix table

fallback to previous longest prefix on mismatch while building prefix table

if pattern[i] == pattern[j]: j += 1 prefix[i] = j

extend current prefix length when characters match

while j > 0 and text[i] != self.pattern[j]: j = self.prefix_table[j - 1] # fallback on mismatch

fallback in pattern index on mismatch during search

if text[i] == self.pattern[j]: j += 1

advance pattern index on match

if j == len(self.pattern): result.append(i - j + 1) # match found j = self.prefix_table[j - 1] # continue searching

record match start index and reset pattern index to find next matches

Output

Pattern found at indices: 10

Complexity Analysis

Time: O(n + m) because building the prefix table takes O(m) and searching takes O(n), where n is text length and m is pattern length

Space: O(m) for storing the prefix table of the pattern

vs Alternative: Naive search is O(n*m) because it restarts from scratch on mismatch; KMP avoids rechecking by using prefix table, making it faster

Edge Cases

Empty pattern

Returns empty list immediately, no matches

DSA Python

if j == len(self.pattern):

Pattern longer than text

No matches found, returns empty list

DSA Python

for i in range(len(text)):

Pattern equals text

Returns [0] as match at start

DSA Python

if j == len(self.pattern):

When to Use This Pattern

When you need to find a pattern inside a text efficiently and want to avoid rechecking characters after mismatches, use KMP pattern matching because it uses a prefix table to jump smartly.

Common Mistakes

Mistake: Not updating the pattern index j correctly after a mismatch, causing infinite loops or missed matches
Fix: Always fallback j to prefix_table[j-1] on mismatch inside the while loop

Mistake: Building prefix table incorrectly by not handling fallback properly
Fix: Use a while loop to fallback j until characters match or j is zero

Summary

KMP finds all occurrences of a pattern in a text efficiently by using a prefix table to skip unnecessary comparisons.

Use KMP when you want fast pattern searching especially for large texts and repeated patterns.

The key insight is the prefix table that tells how far to jump back in the pattern on mismatch, avoiding rechecking characters.

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