1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #define N 1000005 5 using namespace std; 6 int next[N]; 7 char s1[N],s2[N]; 8 int len1,len2,ans; 9 void getnext(int plen){10     int i = 0,j = -1;11     next[0] = -1;12     while( i<plen ){13         if(j==-1||s1[i]==s1[j]){14             ++i;++j;15           if(s1[i]!=s1[j] )16             next[i] = j;17           else18             next[i] = next[j];19         }20         else21             j = next[j];22     }23 }24 void KMP(){25     getnext(len1);26     int i = 0,j = 0;27     while (i<len2&&j<len1){28         if( j == -1 || s2[i] == s1[j] ){29             ++i;30             ++j;31         }32         else {33             j = next[j];34 35         }36          if( j==len1 ){//找到一个匹配串之后，不是在原来串中往后移动一位，而是移动i-(j-next[j]);37             ans++;38             j=next[j];39          }40     }41 }42 int main(){43     int k;44     scanf("%d",&k);45     while(k--){46         scanf("%s%s",s1,s2);47         len1=strlen(s1);48         len2=strlen(s2);49         ans=0;50         KMP();51         printf("%d\n",ans);52     }53 }