kmp string matching algorithm in DAA
Here you will learn the program code of kmp string matching algorithm in c programming.
The Knuth-Morris-Pratt (KMP) algorithm is a more efficient string matching algorithm compared to the Naive String Matching algorithm. It utilizes information from previous comparisons to avoid unnecessary comparisons. Here’s how it works:
- Preprocess the pattern to determine the longest prefix which is also a suffix for each prefix substring. This information is stored in an array called the “prefix function” or “failure function.”
- Use this prefix function to guide the matching process while scanning the text.
- When a mismatch occurs, instead of starting over from the beginning of the pattern, the algorithm shifts the pattern by an amount determined by the prefix function.
This algorithm has a time complexity of O(n + m), where n is the length of the text and m is the length of the pattern.
kmp string matching algorithm example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <stdio.h> #include <string.h> void computePrefixFunction(char pattern[], int prefix[], int m) { int k = 0; prefix[0] = 0; for (int q = 1; q < m; q++) { while (k > 0 && pattern[k] != pattern[q]) { k = prefix[k - 1]; } if (pattern[k] == pattern[q]) { k++; } prefix[q] = k; } } int KMPStringMatch(char text[], char pattern[]) { int n = strlen(text); int m = strlen(pattern); int prefix[m]; computePrefixFunction(pattern, prefix, m); int j = 0; for (int i = 0; i < n; i++) { while (j > 0 && text[i] != pattern[j]) { j = prefix[j - 1]; } if (text[i] == pattern[j]) { j++; } if (j == m) { return i - m + 1; // Match found at position i - m + 1 } } return -1; // Match not found } int main() { char text[100]; char pattern[20]; printf("Enter a sentance : "); gets(text); printf("Enter Pattern to found with position : "); gets(pattern); int pos = KMPStringMatch(text, pattern); if (pos != -1) { printf("Pattern found at position: %d\n", pos); } else { printf("Pattern not found in the text.\n"); } return 0; } |
Output
Enter a sentance : This is a simple example of the KMP String Matching algorithm @coderevise.com
Enter Pattern to found with position : KMP
Pattern found at position: 32
Read Also