Learn how to implement the Naive Pattern Matching Algorithm in C programming language using functions and for loop. The pattern matching algorithm is also known as String Searching Algorithm.
What is Pattern Matching Algorithm?
The Naive String Matching Algorithm is one of the simplest methods to check whether a string follows a particular pattern or not.
It is simple of all the algorithm but is highly inefficient. It checks where the string matches the input pattern one by one with every character of the string.
The complexity of the Naive String Search Algorithm for average case scenario is O(n +m) whereas for worst case scenario is O(nm).
The following Naive String Search program takes a string from the user and then a pattern that user wants to find in the string.
If the pattern is found in the string, it will display the position where the pattern matched in the string.
There are many other algorithms primarily developed for pattern matching or string matching requirements. Some of them are as follows:
- Boyer Moore Search Algorithm
- Rabin Karp String Search Algorithm
- Two Way String Matching Algorithm
- Backward Non-Deterministic Dawg Matching Algorithm
- Finite State Automation Algorithm
- Knuth Morris Prat Algorithm
Must Read: C Program To Find Permutations of a String using Recursion
Method 1: C Program For Naive Pattern Matching Algorithm using For Loop
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 | #include<stdio.h> #include<string.h> int main() { int str_length, pattern_length, j, i, count = 0; char str[30], pattern[30] ; printf("\nEnter a String:\t"); scanf("%s", str); printf("\nEnter a Pattern to Match:\t"); scanf("%s", pattern); str_length = strlen(str); pattern_length = strlen(pattern); printf("\nPattern Matched at Position:\t"); for(i = 0; i < str_length - pattern_length; i++) { for(j = 0; j < pattern_length; j++) { if(str[i + j] == pattern[j]) count++; } if(count == pattern_length) { printf("%d\t", i); } count = 0; } printf("\n"); return 0; } |
Must Read: C Program To Find Longest Common Subsequence
Method 2: C Program For Naive String Matching Algorithm using Function
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 | #include<stdio.h> #include<string.h> void pattern_matching(char *str, char *pattern); int main() { char str[30], pattern[30]; printf("\nEnter a String:\t"); scanf("%s", str); printf("\nEnter a Pattern to Match:\t"); scanf("%s", pattern); pattern_matching(str, pattern); return 0; } void pattern_matching(char *str, char *pattern) { int pattern_length = strlen(pattern); int str_length = strlen(str); for(int m = 0; m <= str_length - pattern_length; m++) { int n; for(n = 0; n < pattern_length; n++) if(str[m + n] != pattern[n]) { break; } if(n == pattern_length) { printf("Pattern Matched at Position:\t%d\n", m); } } } |
Must Read: C Program To Compare Two Strings
Output
Enter a String: CodingAlpha
Enter a Pattern to Match: in
Pattern Matched at Position: 3
If you have any compilation error or doubts in this Naive Pattern Matching program in C language, let us know about it in the comment section below.
Amazing. I didn’t knew string pattern matching could be so simple. Thanks guys.
Please upload Knuth Morris Prat algorithm for pattern matching in C programming.