数据结构复习之kmp算法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 char s1[100001],s2[1000001];
 5 int next[1000001];
 6 int main()
 7 {
 8     int i,j,t,len1,len2;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%s%s",s1,s2);
13         len1 = strlen(s1);
14         len2 = strlen(s2);
15         j = -1;
16         next[0] = -1;
17         for(i = 1;i < len1;i ++)
18         {
19             while(j >= 0&&s1[j+1] != s1[i])
20             j = next[j];
21             if(s1[j+1] == s1[i]) j ++;
22             next[i] = j;
23         }
24         j = -1;
25         int ans = 0;
26         for(i = 0;i < len2;i ++)
27         {
28             while(j >= 0&&s1[j+1] != s2[i])
29             j = next[j];
30             if(s1[j+1] == s2[i]) j ++;
31             if(j == len1 - 1)
32             {
33                 j = next[j];
34                 ans ++;
35             }
36         }
37         printf("%d\n",ans);
38     }
39     return 0;
40 }