KMP code by ACcreator
#include<stdio.h>
#include<string.h>
char A[10001];
char B[1000001];
int Q[10001];
int n;
int main(void)
{
int i, j, k, l, m;
int ans;
scanf("%d", &n);
for(l=0; l<n; l++)
{
ans = 0;
scanf("%s%s", A, B);
Q[0] = -1; j = -1; m = strlen(A);
for(i=1; i<m; i++)
{
while(j>=0 && A[j+1]!=A[i]) j=Q[j];
if(A[j+1]==A[i]) j++;
Q[i] = j;
}
k = strlen(B); j = -1;
for(i=0; i<k; i++)
{
while(j>=0 && A[j+1]!=B[i]) j=Q[j];
if(A[j+1]==B[i]) j++;
if(j == m-1)
{
ans ++;
j = Q[j];
}
}
printf("%d\n", ans);
}
return 0;
}
My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.