基础KMP 开始学AC自动机了 先搞清楚KMP
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000010;
char a[maxn], p[maxn];
int f[maxn];
void getFail()
{
int m = strlen(p);
f[0] = f[1] = 0;
for(int i = 1; i < m; i++)
{
int j = f[i];
while(j && p[i] != p[j])
j = f[j];
f[i+1] = p[i] == p[j] ? j+1 : 0;
}
}
void find()
{
int cnt = 0;
int j = 0;
int n = strlen(a);
int m = strlen(p);
for(int i = 0; i < n; i++)
{
while(j && a[i] != p[j])
j = f[j];
if(a[i] == p[j])
j++;
if(j == m)
cnt++;
}
printf("%d\n", cnt);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s %s", p, a);
getFail();
find();
}
return 0;
}
POJ 3461 Oulipo / KMP,布布扣,bubuko.com
原文：http://blog.csdn.net/u011686226/article/details/21965991