KMP Pattern Matching Algorithm in DSA C# - Build from Scratch

KMP Pattern Matching Algorithm

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

🎯 Goal: Build the KMP (Knuth-Morris-Pratt) pattern matching algorithm step-by-step to find all occurrences of a pattern string inside a text string.

📋 What You'll Learn

Create a function to build the longest prefix suffix (LPS) array for the pattern

Use the LPS array to efficiently search the pattern in the text

Return all starting indices where the pattern is found in the text

💡 Why This Matters

🌍 Real World

Pattern matching is used in text editors, search engines, DNA sequence analysis, and network security to find specific sequences quickly.

💼 Career

Understanding KMP algorithm is important for software engineers working on search features, bioinformatics, and performance-critical string processing.

1

Create the pattern and text strings

Create two string variables called text and pattern with these exact values: text = "ABABDABACDABABCABAB" and pattern = "ABABCABAB".

DSA C#

# Your code here

Hint

Use string type and assign the exact values given.

2

Build the LPS (Longest Prefix Suffix) array

Create a function called BuildLPS that takes a string pattern and returns an integer array lps. Initialize lps with the length of pattern. Use variables length and i to build the LPS array following the KMP preprocessing logic.

DSA C#

string text = "ABABDABACDABABCABAB";
string pattern = "ABABCABAB";

// Your code here

Hint

Follow the KMP preprocessing steps: compare characters, update length, and fill lps array.

3

Implement the KMP search function

Create a function called KMPSearch that takes text and pattern strings. Use the BuildLPS function to get the LPS array. Use variables i and j to iterate over text and pattern. Collect all starting indices of matches in a list called result.

DSA C#

string text = "ABABDABACDABABCABAB";
string pattern = "ABABCABAB";

int[] BuildLPS(string pattern)
{
    int length = 0;
    int i = 1;
    int[] lps = new int[pattern.Length];
    lps[0] = 0;

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

// Your code here

Hint

Use two pointers i and j to scan text and pattern. Use the lps array to skip unnecessary comparisons.

4

Print all starting indices of pattern matches

Call the KMPSearch function with text and pattern. Store the result in a variable called matches. Print the matches list as a comma-separated string using string.Join(", ", matches).

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string text = "ABABDABACDABABCABAB";
        string pattern = "ABABCABAB";

        int[] BuildLPS(string pattern)
        {
            int length = 0;
            int i = 1;
            int[] lps = new int[pattern.Length];
            lps[0] = 0;

            while (i  KMPSearch(string text, string pattern)
        {
            int[] lps = BuildLPS(pattern);
            List result = new List();
            int i = 0; // index for text
            int j = 0; // index for pattern

            while (i < text.Length)
            {
                if (pattern[j] == text[i])
                {
                    i++;
                    j++;
                }

                if (j == pattern.Length)
                {
                    result.Add(i - j);
                    j = lps[j - 1];
                }
                else if (i < text.Length && pattern[j] != text[i])
                {
                    if (j != 0)
                        j = lps[j - 1];
                    else
                        i++;
                }
            }
            return result;
        }

        // Your code here
    }
}

Hint

Call KMPSearch(text, pattern), store in matches, then print using Console.WriteLine(string.Join(", ", matches)).

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