hiho 1015 KMP

input

1<=T<=20

string1 1<=strlen(string1)<=1e4

string2 2<=strlen(string2)<=1e6

output

string1在string2出现的次数

在第i位不匹配时跳到idx[i-1]位继续匹配

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <ctime>
11 #include <cmath>
12 
13 using namespace std;
14 
15 const int N=1e6+10;
16 int idx[N],T;
17 char a[N],b[10010];
18 
19 void Next()
20 {
21     idx[0]=0;
22     for(int i=1,j=0;b[i];i++)
23     {
24         while(j&&b[i]!=b[j])
25             j=idx[j-1];
26         b[i]==b[j]?idx[i]=++j:idx[i]=j;
27     }
28 }
29 
30 int kmp()
31 {
32     int c=0,i,j;
33     for(i=0,j=0;a[i];i++)
34     {
35         if(!b[j]) c++;
36         if(a[i]!=b[j])
37         {
38             while(j)
39             {
40                 j=idx[j-1];
41                 if(b[j]==a[i])
42                 {
43                     j++;
44                     break;
45                 }
46             }
47         }
48         else j++;
49     }
50     if(!b[j]) c++;
51     return c;
52 }
53 
54 int main()
55 {
56     //freopen("/home/user/桌面/in","r",stdin);
57     scanf("%d",&T);
58     while(T--)
59     {
60         scanf("%s%s",b,a);
61         Next();
62         //for(int i=0;b[i];i++) printf("%d ",idx[i]);printf("
");
63         printf("%d
",kmp());
64     }
65     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
66     return 0;
67 }

View Code