思路：模板题，在匹配成功后，因为下一个匹配到的位置的前缀可能是前一个匹配到的位置的后缀，所以每匹配成功执行i = next[i]。
#include <cstdio> #include <cstring> using namespace std; char s[1000005], p[10005]; int sl, pl, next[10005]; void get_next(){ int i = 0,j = -1; next[0] = -1; while(i < pl) { if(j == -1 || p[i] == p[j]) next[++i] = ++j; else j = next[j]; } } int kmp(){ sl = strlen(s); pl = strlen(p); get_next(); int i = 0, j = 0, cnt = 0; while(j < sl){ if(i == -1 || p[i] == s[j]){ ++i; ++j; } else{ i = next[i]; } if(i == pl){ ++cnt; i = next[i]; } } return cnt; } int main() { int n; scanf("%d", &n); getchar(); while(n--){ gets(p); gets(s); printf("%d\n", kmp()); } return 0; }