C program for Naive String Matching
The naive string matching algorithm is a brute force algorithm. The complexity is O((n-m)*m). The algorithm is simple but inefficient. Starting from the first character of the original text (text[0]), the pattern is compared with the substring obtained from text[0] to text[length_of_pattern]. If it does not match, then we shift to the next substring, i.e., from text[1] to text[1+length_of_pattern], and so on till either the string is matched, or the limit (substring length is less than length_of_pattern) is reached.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void string_match(char *text, char *pattern)
{
int len1,len2,i,j,count=0;
len1 = strlen(text);
len2 = strlen(pattern);
if(len2>len1)
{
printf("Pattern cannot be longer than the original text.");
return;
}
for(i=0;i<len1-len2;i++)
{
for(j=0;j<len2;j++)
{
if(text[i+j]==pattern[j])
count++;
}
if(count==len2-1)
printf("position:%d\t",i+1);
count=0;
}
}
int main()
{
char str1[50],str2[50];
printf("\t\tNaive String Matching\n");
printf("Enter the original text:");
fgets(str1,50,stdin);
printf("Enter the pattern to be matched:");
fgets(str2,50,stdin);
string_match(str1,str2);
return 0;
}
