Naive String Matching algorithm in DAA
The Naive String Matching algorithm is a simple method used to find occurrences of a pattern within a text.
Here’s how it works:
1. Start with the first character of the text.
2. Compare it with the first character of the pattern.
3. If they match, compare the next characters of both text and pattern.
4. If at any point a mismatch is found, shift the pattern one position to the right and start over from step 2.
5. Repeat this process until either the end of the text is reached or a complete match is found.
Naive String Matching algorithm in pseudocode:
1 2 3 4 5 6 7 8 9 10 11 | NaiveStringMatch(text, pattern): n = length of text m = length of pattern for i from 0 to n - m: j = 0 while j < m and text[i+j] = pattern[j]: j = j + 1 if j = m: return i // Match found at position i return -1 // Match not found |
In this pseudocode:
‘text’ is the input text where you want to find occurrences of the pattern.
‘pattern’ is the string you’re searching for within the text.
‘n’ is the length of the text.
‘m’ is the length of the pattern.
This algorithm has a time complexity of O((n-m+1)*m), where n is the length of the text and m is the length of the pattern.
Program code of Naive String Matching algorithm in DAA
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 | #include <stdio.h> #include <string.h> int naiveStringMatch(char text[], char pattern[]) { int n = strlen(text); int m = strlen(pattern); for (int i = 0; i <= n - m; i++) { int j; for (j = 0; j < m; j++) { if (text[i + j] != pattern[j]) break; } if (j == m) return i; // If mached at position i } return -1; // if not Matched } 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 = naiveStringMatch(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 Naive String Matching algorithm @ coderevise.com
Enter Pattern to found with position : String
Pattern found at position: 38
Read Also
Matrix Chain Multiplication in C