https://vjudge.net/problem/HDU-1686

题意：

求模板串在文本串中出现的次数。

思路：

果果的kmp模板题啊，所以直接上模板啦。用的是lrj大大的白书的模板。

代码：

1 #include 
     
       2 #include 
      
        3  4 char text[1000005]; 5 char w[10005]; 6 int fl[1000005]; 7  8 void getfail(char *P,int *f) 9 {10     int m = strlen(P);11     f[0] = 0;f[1] = 0;12 13     for (int i = 1;i < m;i++)14     {15         int j = f[i];16 17         while (j && P[i] != P[j]) j = f[j];18 19         f[i+1] = P[i] == P[j] ? j+1 : 0;20     }21 }22 23 int find(char *T,char *P,int *f)24 {25     int ans = 0;26     int n = strlen(T),m = strlen(P);27 28     getfail(P,f);29 30     int j = 0;31 32     for (int i = 0;i < n;i++)33     {34         while (j && P[j] != T[i]) j = f[j];35         if (P[j] == T[i]) j++;36         if (j == m) ans++;37     }38 39     return ans;40 }41 42 int main()43 {44     int t;45 46     scanf("%d",&t);47 48     while (t--)49     {50         memset(fl,0,sizeof(fl));51 52         scanf("%s",w);53         scanf("%s",text);54 55         int ans = find(text,w,fl);56 57         printf("%d\n",ans);58     }59 60     return 0;61 }