Post
Ask Question

Naive Pattern Search Algorithm

  1. //Implementation of Naive Pattern Search Algorithm  
  2. #include<stdio.h>  
  3. #include<conio.h>  
  4. #include<string.h>  
  5.   
  6. void Naive_Search_Algo(char *search_pattern,char *original_pattern  
  7. {  
  8.    int m=strlen(search_pattern);  
  9.    int n=strlen(original_pattern);  
  10.    int i,j;  
  11.    for(i=0;i<n-m;i++)  
  12.    {  
  13.       for(j=0;j<m;j++)  
  14.       {  
  15.          if(original_pattern[i+j]!=search_pattern[j])  
  16.             break;  
  17.          if(j==m)  
  18.             printf("\n Searching String Is Founf At %d Location",i);  
  19.       }  
  20.    }  
  21. }  
  22.    
  23. int main()  
  24. {  
  25.    char search_pattern[100];  
  26.    char original_pattern[100];  
  27.    printf("\n Enter Original String");  
  28.    scanf("%s",original_string);  
  29.    printf("\n Enter Searching String");  
  30.    scanf("%s",Search_pattern);  
  31.    Naive_search_Algo(search_pattern,original_pattern);  
  32.    return 0;  
  33. }  
Algorithm of Naive pattern Search Algo
 
Searching for p in string t,
  1. for i from 0 to n-m :  
  2.    for j from 0 to m-1:  
  3.       if p[j]! = t[i+j]  
  4.          break out of inner loop  //p is not t[i..i+(m-1)]  
  5.       if j==m:  
  6.          return i  
  7.  return-1  //no match found if we reach this point   
Worst - case complexity: Θ(mn), where m is the length of p and n is the length of  t.