[模板]KMP字符串匹配

洛谷P3375

注意：两次过程大致相同，故要熟读熟记，切勿搞混

　　　可以看看其他的教程：http://www.cnblogs.com/c-cloud/p/3224788.html

　　　本来就不太熟，若是在记不住，就放弃

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define man 1000010
 4 string p,t;
 5 int next[man];
 6 inline void makenext()
 7 {    int q,k;
 8     int m=p.size();
 9     next[0]=0;
10     for(q=1,k=0;q<m;q++)
11     {    while(k>0&&p[q]!=p[k])
12             k=next[k-1];
13         if(p[q]==p[k])
14             k++;
15         next[q]=k;
16         }
17     }
18 inline void kmp()
19 {    int n,m;
20     n=t.size();
21     m=p.size();
22     makenext();
23     for(int i=0,k=0;i<n;i++)
24     {    while(k>0&&p[k]!=t[i])
25         k=next[k-1];
26         if(p[k]==t[i])
27             k++;
28         if(k==m)
29             cout<<(i-m+1+1)<<endl;//从零开始计数时，整体数值加一（因为题目要求从一开始计数） 
30         }
31     }
32 int main()
33 {    cin>>t>>p;
34     kmp();
35     for(int i=0;i<p.size();i++)
36         cout<<next[i]<<" ";
37     cout<<endl;
38     return 0;
39     }