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.