POJ--3461

分析：求一个串在另一个串中出现的次数，显然用KMP可以解决。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn1 10005
 5 #define maxn2 1000005
 6 using namespace std;
 7 char s[maxn1],t[maxn2];
 8 int next[maxn1],sum,len1,len2;
 9 void get_next()
10 {
11     int i,j;len1=strlen(s);
12     next[0]=-1;
13     i=0;j=-1;
14     while(i<len1){
15         if(j==-1||s[i]==s[j]){
16             i++;j++;
17             next[i]=j;
18         }
19         else j=next[j];
20     }
21 }
22 void kmp()
23 {
24     sum=0;
25     get_next();
26     int i=-1,j=-1;len2=strlen(t);
27     while(i<len2){
28         if(j==-1||t[i]==s[j])
29         {
30             i++;j++;
31         }
32         else j=next[j];
33         if(j==len1){
34                sum++;   
35             j=next[j];
36         }
37     }
38 }
39 int main()
40 {
41     int T;
42     scanf("%d",&T);
43     while(T--)
44     {
45         scanf("%s%*c%s",s,t);
46         kmp();
47         printf("%d
",sum);
48     }
49     return 0;
50 }
View Code