http://acm.hdu.edu.cn/showproblem.php?pid=1686
#include <iostream> #include <cstring> #include <cstdio> using namespace std; char w[15000]; char t[1000005]; int next[15000]; void get_next() { int l=strlen(w); int i,j; i=0;next[0]=-1;j=-1; while(i<l) { if(j==-1||w[i]==w[j]) { i++; j++; next[i]=j; } else j=next[j]; } } int kmp() { int l2=strlen(w); int l1=strlen(t); int i=0; int j=0; int s=0; while(i<l1) { if(j==-1||w[j]==t[i]) { i++; j++; } else j=next[j]; if(j>=l2) { j=next[j]; //关键 s++; } } return s; } int main() { int c; scanf("%d",&c); while(c--) { scanf("%s%s",w,t); get_next(); int k=kmp(); printf("%d\n",k); } return 0; }