【KMP模板】POJ3461-Oulipo

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int MAXN=1000000+50;
 7 const int MAXM=10000+50; 
 8 char t[MAXN],p[MAXN];
 9 int next[MAXM];
10 int lent,lenp;
11 
12 void getnext()
13 {
14     int i=0,j=-1;
15     next[i]=j;
16     while (i<lenp)
17     {
18         if (j==-1 || p[i]==p[j]) next[++i]=++j;
19             else j=next[j];
20     }
21 }
22 
23 int getans()
24 {
25     int i=0,j=0,ans=0;
26     while (i<lent)
27     {
28         if (t[i]==p[j] || j==-1)
29         {
30             i++;
31             j++;
32         }
33         else j=next[j];
34         if (j==lenp)//如果匹配成功，则视作这次匹配失败，返回到上一次。 
35         {
36             ans++;
37             j=next[j-1];
38             i--;
39         }
40     }
41     return ans;
42 }
43 
44 int main()
45 {
46     int kase;
47     scanf("%d",&kase);
48     for (int i=0;i<kase;i++)
49     {
50         scanf("%s%s",p,t);
51         lent=strlen(t); 
52         lenp=strlen(p);//注意一定要先把strlen存下来，否则会TLE！ 
53         getnext();
54         cout<<getans()<<endl;
55     }
56     return 0;
57 }