裸KMP
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 100010; char s[MAXN],s1[MAXN * 10]; int next[MAXN],num[MAXN]; void Get_N(int l){ memset(next,0,sizeof(next)); for(int i = 1;i < l;i++){ int j = next[i]; while(j && s[i] != s[j]) j = next[j]; if(s[i] == s[j]) next[i + 1] = j + 1; else next[i + 1] = 0; } } void Kmp(){ int cnt = 0,j = 0; int m = strlen(s),n = strlen(s1); Get_N(m); for(int i = 0;i < n;i++){ while(j && s1[i] != s[j]) j = next[j]; if(s1[i] == s[j]) j++; if(j == m){ cnt++; j = next[j]; } } printf("%d\n",cnt); } int main(){ int T; while(~scanf("%d",&T)){ while(T--){ scanf("%s",s); scanf("%s",s1); Kmp(); } } return 0; }