KMP Pattern Matching Algorithm in DSA C#

Mental Model

KMP finds a pattern in text by remembering where to restart after a mismatch, avoiding repeated checks.

Analogy: Like reading a book and marking where a sentence starts so if you lose your place, you jump back to the last known start instead of rereading everything.

Text:  A B A B A B C A B A B D
Pattern:    A B A B D
Prefix table: [0,0,1,2,0]

Dry Run Walkthrough

Input: text: "ABABABCABABD", pattern: "ABABD"

Goal: Find the starting index of the pattern "ABABD" in the text using KMP.

Step 1: Build prefix table for pattern

Pattern: A B A B D
Prefix table: [0,0,1,2,0]

Why: Prefix table tells where to restart in pattern after mismatch

Step 2: Compare text[0] 'A' with pattern[0] 'A', match, advance both

Text: [A] B A B A B C A B A B D
Pattern: [A] B A B D

Why: Start matching from beginning

Step 3: Compare text[1] 'B' with pattern[1] 'B', match, advance both

Text: A [B] A B A B C A B A B D
Pattern: A [B] A B D

Why: Continue matching

Step 4: Compare text[2] 'A' with pattern[2] 'A', match, advance both

Text: A B [A] B A B C A B A B D
Pattern: A B [A] B D

Why: Continue matching

Step 5: Compare text[3] 'B' with pattern[3] 'B', match, advance both

Text: A B A [B] A B C A B A B D
Pattern: A B A [B] D

Why: Continue matching

Step 6: Compare text[4] 'A' with pattern[4] 'D', mismatch, use prefix table to shift pattern index to 0

Text: A B A B [A] B C A B A B D
Pattern: [A] B A B D

Why: Mismatch, restart pattern from prefix table position

Step 7: Compare text[4] 'A' with pattern[0] 'A', match, advance both

Text: A B A B A [B] C A B A B D
Pattern: A [B] A B D

Why: Restart matching from pattern start

Step 8: Continue matching until text[10] 'D' matches pattern[4] 'D', full pattern matched

Text: A B A B A B C A B A [B D]
Pattern: A B A B [D]

Why: Pattern found at index 7 in text

Result:

Final match found at index 7 in text: A B A B A B C A B A B D

Annotated Code

DSA C#

using System;

class KMPMatcher
{
    public static int[] BuildPrefixTable(string pattern)
    {
        int[] prefix = new int[pattern.Length];
        int j = 0;
        for (int i = 1; i < pattern.Length; i++)
        {
            while (j > 0 && pattern[i] != pattern[j])
                j = prefix[j - 1];
            if (pattern[i] == pattern[j])
                j++;
            prefix[i] = j;
        }
        return prefix;
    }

    public static int KMPSearch(string text, string pattern)
    {
        if (pattern.Length == 0) return 0;
        int[] prefix = BuildPrefixTable(pattern);
        int j = 0;
        for (int i = 0; i < text.Length; i++)
        {
            while (j > 0 && text[i] != pattern[j])
                j = prefix[j - 1];
            if (text[i] == pattern[j])
                j++;
            if (j == pattern.Length)
                return i - j + 1;
        }
        return -1;
    }

    static void Main()
    {
        string text = "ABABABCABABD";
        string pattern = "ABABD";
        int index = KMPSearch(text, pattern);
        if (index != -1)
            Console.WriteLine($"Pattern found at index {index}");
        else
            Console.WriteLine("Pattern not found");
    }
}

while (j > 0 && pattern[i] != pattern[j]) j = prefix[j - 1];

Backtrack pattern index using prefix table on mismatch during prefix table build

if (pattern[i] == pattern[j]) j++;

Advance prefix length when characters match

while (j > 0 && text[i] != pattern[j]) j = prefix[j - 1];

Backtrack pattern index using prefix table on mismatch during search

if (text[i] == pattern[j]) j++;

Advance pattern index on match

if (j == pattern.Length) return i - j + 1;

Full pattern matched, return start index in text

Output

Pattern found at index 7

Complexity Analysis

Time: O(n + m) because we build prefix table in O(m) and search text in O(n) without rechecking characters

Space: O(m) for prefix table storing longest prefix lengths for pattern

vs Alternative: Naive search is O(n*m) because it restarts from next text character on mismatch; KMP avoids this by using prefix table

Edge Cases

Empty pattern

Returns 0 immediately as empty pattern matches at start

DSA C#

if (pattern.Length == 0) return 0;

Pattern longer than text

Returns -1 as pattern cannot be found

DSA C#

for (int i = 0; i < text.Length; i++)

No match in text

Returns -1 after full search

DSA C#

return -1;

When to Use This Pattern

When you need to find a substring efficiently and want to avoid rechecking characters after mismatch, use KMP pattern matching because it uses a prefix table to skip unnecessary comparisons.

Common Mistakes

Mistake: Not updating the pattern index correctly after mismatch using prefix table
Fix: Use the prefix table to reset pattern index j = prefix[j - 1] inside the while loop on mismatch

Mistake: Building prefix table incorrectly by not handling the while loop for backtracking
Fix: Include while loop to backtrack j using prefix table when characters don't match during prefix table construction

Summary

Finds pattern in text efficiently by using a prefix table to avoid repeated comparisons after mismatches.

Use when you need fast substring search in large texts without checking all characters repeatedly.

Remember the prefix table tells where to restart in the pattern after a mismatch, saving time.

Practice

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

easy

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

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To calculate the factorial of a number recursively

Solution

1. Step 1: Understand the goal of KMP

   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 calculating factorials are unrelated to pattern searching.

3. Final Answer:

   To find occurrences of a pattern string within a text efficiently -> Option A

4. Quick Check:

   KMP = Pattern searching [OK]

Hint: KMP is all about fast pattern search in text [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates factorials

2. Which of the following is the correct way to declare the prefix table (lps array) in C# for KMP algorithm?

easy

A. int[] lps = new int();

B. int lps = new int[pattern.Length];

C. int lps[] = new int[pattern.Length];

D. int[] lps = new int[pattern.Length];

Solution

1. Step 1: Understand array declaration in C#

   In C#, arrays are declared with type[], then new type[size]. So int[] lps = new int[pattern.Length]; is correct.

2. Step 2: Check other options

   int lps = new int[pattern.Length]; misses [] for array type, C uses invalid syntax, D uses C/C++ style which is invalid in C#.

3. Final Answer:

   int[] lps = new int[pattern.Length]; -> Option D

4. Quick Check:

   C# array syntax = int[] name = new int[size]; [OK]

Hint: Use int[] for arrays, not int alone [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using C/C++ style array declaration in C#
• Trying to instantiate array without size

3. What will be the output of the following C# code snippet using KMP algorithm to find pattern "ABABC" in text "ABABABC"?

string text = "ABABABC";
string pattern = "ABABC";
List<int> matches = KMPSearch(pattern, text);
Console.WriteLine(string.Join(",", matches));

// Assume KMPSearch returns list of start indices where pattern matches text

medium

A. 0,2

B. 1

C. 2

D. No matches

Solution

1. Step 1: Analyze the text and pattern

   Text: A B A B A B C Pattern: A B A B C Check where pattern fully matches text starting index.

2. Step 2: Find matching index

   At index 0: text substring "ABABA" does not match "ABABC" (last char mismatch) At index 1: substring "BABAB" no match At index 2: substring "ABABC" matches pattern exactly.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substring matches carefully for exact pattern [OK]

Common Mistakes:

• Assuming multiple matches without checking full pattern
• Off-by-one errors in indexing
• Confusing partial matches as full matches

4. Identify the bug in this KMP prefix table (lps) computation code snippet in C#:

int[] ComputeLPS(string pattern) {
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;
    while (i < pattern.Length) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

medium

A. Incorrect update of length in else block: should be length = lps[length - 1];

B. Wrong initialization of lps array size

C. Using while loop instead of for loop causes infinite loop

D. Missing return statement at the end

Solution

1. Step 1: Understand lps update logic

   When mismatch occurs and length != 0, length should be updated to lps[length - 1], not lps[length].

2. Step 2: Check other parts

   Array size is correct, while loop is valid, return statement exists. So only length update is wrong.

3. Final Answer:

   Incorrect update of length in else block: should be length = lps[length - 1]; -> Option A

4. Quick Check:

   lps update uses length-1 index [OK]

Hint: Use length-1 index when updating length on mismatch [OK]

Common Mistakes:

• Using lps[length] instead of lps[length - 1]
• Confusing loop types causing infinite loops
• Forgetting to return lps array

5. Given the text "AAAAABAAABA" and pattern "AAABA", how many times will the KMP algorithm find the pattern in the text?

hard

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Identify all occurrences of pattern in text

   Text: A A A A A B A A A B A Pattern: A A A B A Check each possible start index:

2. Step 2: Check matches at each index

   Index 0: substring "AAAAA" no (pattern ends with B) Index 1: substring "AAAAB" no (pattern ends with A) Index 2: substring "AAABA" yes (match 1) Index 3: substring "AABAA" no Index 4: substring "ABAAA" no Index 5: substring "BAAAB" no Index 6: substring "AAABA" yes (match 2) Index 7: substring "AABA" incomplete Index 8: substring "ABA" incomplete Check carefully for overlapping matches.

3. Step 3: Re-check for missed matches

   Check index 1 carefully: substring "AAAAB" pattern is "AAABA" so no match. Check index 0 carefully: substring "AAAAA" pattern ends with B, no match. Check index 6: "AAABA" matches pattern exactly (match 2). Check index 2: "AAABA" matches pattern exactly (match 1). No other matches found.

4. Step 4: Check index 3 for overlapping match

   At index 3: substring "AABAA" does not match pattern "AAABA". At index 4: substring "ABAAA" no match. At index 5: substring "BAAAB" no match. At index 7: substring "AABA" incomplete. So total matches found: 2.

5. Final Answer:

   2 -> Option B

6. Quick Check:

   Pattern found twice in text [OK]

Hint: Check each substring carefully for full pattern match [OK]

Common Mistakes:

• Counting partial matches as full matches
• Missing overlapping matches
• Off-by-one errors in substring indexing