POJ/3461.c

   1 #include <stdio.h>
   2 #include <string.h>
   3
   4 #define maxn 10005
   5 #define maxm 1000005
   6
   7 int next[maxn],n;
   8 char text[maxm],pat[maxn];
   9
  10 inline void get_next() {
  11         int m=strlen(pat),k=-1;
  12         next[0]=-1;
  13         for (int q=1; q<m; q++) {
  14                 while (k>-1 && pat[k+1]!=pat[q]) k=next[k];
  15                 if (pat[k+1]==pat[q]) k++;
  16                 next[q]=k;
  17         }
  18 }
  19
  20 int kmp_match() {
  21         int ans=0,m=strlen(pat),n=strlen(text);
  22         int q=-1;
  23         for (int i=0; i<n; i++) {
  24                 while (q>-1 && pat[q+1]!=text[i]) q=next[q];
  25                 if (pat[q+1]==text[i]) q++;
  26                 if (q==m-1) {
  27                         ans++;
  28                         q=next[q];
  29                 }
  30         }
  31         return ans;
  32 }
  33
  34 int main() {
  35         scanf("%d",&n);
  36         while (n--) {
  37                 scanf("%s%s",pat,text);
  38                 get_next();
  39                 printf("%d\n",kmp_match());
  40         }
  41         return 0;
  42 }