kmp 回忆训练2 poj3461

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int next[1000005];
 6 char str[1000005];
 7 char s[10005];
 8 void initnext(int len)
 9 {
10     int k=0;
11     for(int i=1;i<len;i++)
12     {
13         while(k>0&&s[k]!=s[i]) k=next[k-1];
14         if(s[k]==s[i]) k++;
15         next[i]=k;
16     }
17     return;
18 }
19 int find(int len1,int len2)
20 {
21     int i=0,j=0,ans=0;
22     while(j<len2)
23     {
24         if(s[i]==str[j])
25         {
26             i++;
27             j++;
28             if(i==len1)
29             {
30                 ans++;
31             //    cout<<"i="<<i<<" j="<<j<<endl;
32                 i=next[i-1];
33             }
34         }
35         else if(i==0)
36             j++;
37         else
38             i=next[i-1];
39     }
40     return ans;
41 }
42 int main()
43 {
44     int n;
45     while(~scanf("%d",&n))
46     {
47         while(n--)
48         {
49             scanf("%s",s);
50             scanf("%s",str);
51             int len1=strlen(s),len2=strlen(str);
52             initnext(len1);
53             int ans=find(len1,len2);
54             printf("%d\n",ans);
55         }　　　　
56     }
57     return 0;
58 }