C Programming: Understanding Kernighan's Algorithm (KMP)

beginner
20 min

C Programming: Understanding Kernighan's Algorithm (KMP)

Welcome to our in-depth tutorial on Kernighan-Morris-Pratt (KMP) Algorithm, a powerful pattern searching technique in C programming! This algorithm will help you find patterns within a larger text, making it a useful tool for various applications like text editors, search engines, and more. 🎯

What is KMP Algorithm?

In simple terms, KMP is an efficient string searching algorithm. It allows you to find occurrences of a pattern within a text, even when the pattern can occur anywhere in the text. 💡

Why KMP Algorithm?

  1. Efficient: KMP is faster than the naive method of string searching, making it an ideal choice for large texts.
  2. Versatile: The KMP algorithm can be used in various applications where pattern matching is required.
  3. Backtracking-free: Unlike other algorithms, KMP avoids backtracking, making it more efficient and less prone to errors.

Preparation

Before diving into the KMP algorithm, let's familiarize ourselves with some basic concepts:

  • Character Arrays: Arrays in C to store characters.
  • String Length: A function to get the length of a string.
  • Strstr Function: A built-in C function to find the first occurrence of a substring within a string.

The KMP Algorithm

Now, let's break down the KMP algorithm step by step:

  1. Preprocess: Create an auxiliary function called next[] that stores the length of the longest prefix of the pattern which is also a suffix.

  2. Search: Use the preprocessed next[] array to perform the actual pattern search within the text.

  3. Match: When a match is found, move the pattern and text pointers accordingly.

  4. Continue: Repeat the search and match steps until the entire text is traversed or the pattern is found.

Coding the KMP Algorithm

Here's a complete, working example of the KMP algorithm in C:

c
#include <stdio.h> #include <string.h> void next(char *pat, int m, int *next) { int j = 0; next[0] = -1; for (int i = 1; i < m; i++) { while (j > 0 && pat[i] != pat[j]) j = next[j]; next[i] = j + 1; j = j + next[j]; } } int kmp(char *pat, int m, char *txt, int n) { int i = 0; int j = 0; int next[m]; next(pat, m, next); while (i < n && j < m) { if (j == -1 || txt[i] == pat[j]) { i++; j++; } else { j = next[j]; } } if (j == m) return i - m; // return the starting index of the pattern in the text return -1; // pattern not found } int main() { char txt[] = "ABABABABABCABABAB"; char pat[] = "ABA"; int m = strlen(pat); int n = strlen(txt); printf("Index of the pattern in the text: %d\n", kmp(pat, m, txt, n)); return 0; }

In this example, we've implemented the KMP algorithm and used it to find the occurrence of the pattern "ABA" in the text "ABABABABABCABABAB".

Quiz