montimaj

KMP MATCHER

Apr 11th, 2014
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. void comp_prefix_func(int *p,std::string pat)
  4. {
  5.     int j=0;
  6.     p[0]=0;
  7.     for(int i=1;i<pat.length();++i)
  8.     {
  9.         while(j>0 && pat[j]!=pat[i])
  10.             j=p[j-1];
  11.         if(pat[j]==pat[i])
  12.             j++;
  13.         p[i]=j;
  14.     }
  15. }
  16. void kmp(std::string text,std::string pat)
  17. {
  18.     int n=text.length(),m=pat.length(),j=0,c=0,*p=new int[m];
  19.     comp_prefix_func(p,pat);
  20.     for(int i=0;i<n;++i)
  21.     {
  22.         while(j>0 && pat[j]!=text[i])
  23.             j=p[j-1];
  24.         if(pat[j]==text[i])
  25.             j++;
  26.         if(j==m)
  27.         {
  28.             std::cout<<"Pattern occurs between "<<i-m+1<<" and "<<i<<"\n";
  29.             j=p[j-1];
  30.         }
  31.     }
  32.     delete []p;
  33. }
  34. int main()
  35. {
  36.     std::string s1,s2;
  37.     std::cout<<"Enter two strings: \n";
  38.     std::getline(std::cin,s1);
  39.     std::getline(std::cin,s2);
  40.     kmp(s1,s2);
  41. }
Advertisement
Add Comment
Please, Sign In to add comment