KMP Pattern Matching Algorithm in DSA C - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: Imagine you are building a simple text search tool that finds where a small word (pattern) appears inside a bigger text. This helps in searching documents quickly.

🎯 Goal: You will build the KMP (Knuth-Morris-Pratt) pattern matching algorithm in C. This algorithm finds all starting positions where the pattern appears in the text efficiently.

📋 What You'll Learn

Create an array for the text and an array for the pattern with exact values

Create an array called lps to store longest prefix suffix values

Write a function computeLPSArray to fill the lps array for the pattern

Write a function KMPsearch to find and print all starting indices where the pattern matches the text

Print the matching indices separated by spaces

💡 Why This Matters

🌍 Real World

Text search is used in editors, search engines, and DNA sequence analysis to find patterns quickly.

💼 Career

Understanding KMP algorithm helps in software development roles involving string processing, search optimization, and algorithm design.

1

Create the text and pattern arrays

Create a character array called text with the value "ABABDABACDABABCABAB" and a character array called pattern with the value "ABABCABAB".

DSA C

# Create the text and pattern arrays
// Your code here

Hint

Use double quotes for strings and end with a semicolon.

2

Create the lps array and variables

Create an integer array called lps with size 9 (length of pattern). Create integer variables len and i initialized to 0 and 1 respectively.

DSA C

char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";

// Create lps array and variables
// Your code here

Hint

The lps array size matches the pattern length. Initialize len and i as shown.

3

Write the computeLPSArray function

Write a function void computeLPSArray(char* pattern, int M, int* lps) that fills the lps array. Use a while loop with variables len and i to compute longest prefix suffix values for the pattern.

DSA C

char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";

int lps[9];
int len = 0;
int i = 1;

// Write computeLPSArray function below
// Your code here

Hint

Use the standard KMP lps computation logic with two pointers i and len.

4

Write the KMPsearch function and print matches

Write a function void KMPsearch(char* pattern, char* text) that uses computeLPSArray and finds all starting indices where pattern matches text. Print each matching index followed by a space.

DSA C

char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";

int lps[9];
int len = 0;
int i = 1;

void computeLPSArray(char* pattern, int M, int* lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;
    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// Write KMPsearch function and call it in main
// Your code here

Hint

Use two indexes i and j to scan text and pattern. Print all start positions where pattern matches.

Practice

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

easy

A. To efficiently find occurrences of a pattern in a text without rechecking characters

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the total number of characters in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to find all occurrences of a pattern in a text efficiently.

2. Step 2: Identify how KMP works

   It avoids rechecking characters by using a prefix table to skip unnecessary comparisons.

3. Final Answer:

   To efficiently find occurrences of a pattern in a text without rechecking characters -> Option A

4. Quick Check:

   KMP = Efficient pattern search [OK]

Hint: KMP skips repeated checks using prefix info [OK]

Common Mistakes:

• Thinking KMP sorts or reverses strings
• Confusing KMP with simple substring search
• Assuming KMP counts characters only

2. Which of the following correctly declares the prefix (lps) array in C for KMP algorithm of size m?

easy

A. int *lps = malloc(m * sizeof(int));

B. int lps = new int[m];

C. int lps[m];

D. int lps[] = {m};

Solution

1. Step 1: Understand array declaration in C

   Static arrays like int lps[m]; require constant size or C99 support; dynamic allocation uses malloc.

2. Step 2: Identify correct dynamic allocation

   int *lps = malloc(m * sizeof(int)); correctly allocates memory for m integers dynamically.

3. Final Answer:

   int *lps = malloc(m * sizeof(int)); -> Option A

4. Quick Check:

   Dynamic array = malloc usage [OK]

Hint: Use malloc for dynamic arrays in C [OK]

Common Mistakes:

• Using Java-style array allocation in C
• Incorrect static array size syntax
• Misusing array initialization syntax

3. What will be the output of the following C code snippet using KMP prefix array computation for pattern "ABABC"?

int main() {
    char pattern[] = "ABABC";
    int m = 5, i = 1, len = 0;
    int lps[5] = {0};
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    for (int j = 0; j < m; j++) {
        printf("%d ", lps[j]);
    }
    return 0;
}

medium

A. 0 0 1 2 1

B. 0 1 0 1 2

C. 0 1 2 3 4

D. 0 0 1 2 0

Solution

1. Step 1: Compute lps array step-by-step for "ABABC"

   Index 0: 0; i=1: 'B' != 'A' (len=0) -> lps[1]=0, i=2; i=2: 'A' == 'A' -> len=1, lps[2]=1, i=3; i=3: 'B' == 'B' -> len=2, lps[3]=2, i=4; i=4: 'C' != 'A' (len=2) -> len=lps[1]=0, 'C' != 'A' -> lps[4]=0.

2. Step 2: Final lps array values

   The lps array is [0, 0, 1, 2, 0]. Output: 0 0 1 2 0

3. Final Answer:

   0 0 1 2 0 -> Option D

4. Quick Check:

   lps for "ABABC" = 0 0 1 2 0 [OK]

Hint: Trace lps step-by-step for each pattern char [OK]

Common Mistakes:

• Miscomputing fallback index in lps
• Confusing pattern characters during comparison
• Assuming lps always increases

4. Identify the bug in this KMP prefix array computation snippet and select the fix:

int i = 1, len = 0;
while (i <= m) {
    if (pattern[i] == pattern[len]) {
        len++;
        lps[i] = len;
        i++;
    } else {
        if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
}

medium

A. Remove i++ inside else block

B. Initialize len to 1 instead of 0

C. Change loop condition to i < m

D. Use pattern[len+1] instead of pattern[len]

Solution

1. Step 1: Analyze loop boundary

   The loop runs while i <= m, but array indices go from 0 to m-1, so i == m causes out-of-bounds access.

2. Step 2: Correct loop condition

   Changing condition to i < m prevents accessing beyond array size.

3. Final Answer:

   Change loop condition to i < m -> Option C

4. Quick Check:

   Loop index must be less than array size [OK]

Hint: Loop till less than array size, not equal [OK]

Common Mistakes:

• Using <= instead of < causing overflow
• Incorrect initialization of len
• Misplacing increment statements

5. Given text "ABABDABACDABABCABAB" and pattern "ABABCABAB", how many times does the KMP algorithm find the pattern in the text?

hard

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand pattern occurrences

   Check the text for exact matches of pattern "ABABCABAB" (length 9).

2. Step 2: Locate matches in text

   Pattern matches fully at index 10 ("ABABCABAB" from positions 10-18) and also at index 0 ("ABABDABAC" partial mismatch at 4th char but KMP finds overlapping matches). Actually, KMP finds the pattern twice: once starting at index 0 (partial mismatch but KMP continues) and once at index 10 fully matching. The correct count is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found twice in text [OK]

Hint: Count full pattern matches in text using KMP [OK]

Common Mistakes:

• Counting partial matches as full
• Misidentifying additional matches (e.g., at index 14)
• Overlooking text length boundaries