题意：
求模式串W在母串T中出现的次数，各个匹配串中允许有重叠的部分。
分析：
一开始想不清楚当一次匹配完成时该怎么办，我还SB地让i回溯到某个位置上去。
后来仔细想想，完全不用，直接让模式串向前滑动，即 j = next[j]
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; const int maxn1 = + ;
const int maxn2 = + ;
char W[maxn1], T[maxn2];
int next[maxn1]; void get_next(char* W, int l)
{
int k = -, j = ;
next[] = -;
while(j < l)
{
if(k == - || W[k] == W[j])
{
++k;
++j;
next[j] = k;
}
else k = next[k];
}
} int KMP(char* W, int lenw, char* T, int lent)
{
int i = , j = , ans = ;
while(i < lent)
{
if(j == - || T[i] == W[j])
{
++i;
++j;
}
else j = next[j];
if(j == lenw)
{
ans++;
j = next[j];
}
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin);
int kase;
scanf("%d", &kase);
while(kase--)
{
memset(next, , sizeof(next));
scanf("%s%s", W, T);
int lenw = strlen(W);
int lent = strlen(T);
get_next(W, lenw);
printf("%d\n", KMP(W, lenw, T, lent));
} return ;
}
代码君