Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<string>
- void comp_prefix_func(int *p,std::string pat)
- {
- int j=0;
- p[0]=0;
- for(int i=1;i<pat.length();++i)
- {
- while(j>0 && pat[j]!=pat[i])
- j=p[j-1];
- if(pat[j]==pat[i])
- j++;
- p[i]=j;
- }
- }
- void kmp(std::string text,std::string pat)
- {
- int n=text.length(),m=pat.length(),j=0,c=0,*p=new int[m];
- comp_prefix_func(p,pat);
- for(int i=0;i<n;++i)
- {
- while(j>0 && pat[j]!=text[i])
- j=p[j-1];
- if(pat[j]==text[i])
- j++;
- if(j==m)
- {
- std::cout<<"Pattern occurs between "<<i-m+1<<" and "<<i<<"\n";
- j=p[j-1];
- }
- }
- delete []p;
- }
- int main()
- {
- std::string s1,s2;
- std::cout<<"Enter two strings: \n";
- std::getline(std::cin,s1);
- std::getline(std::cin,s2);
- kmp(s1,s2);
- }
Advertisement
Add Comment
Please, Sign In to add comment