题意：
输入两个字符串，计算二串在一串中出现的次数。
裸裸的KMP，参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。
代码如下：
//light oj 1255 - Substring Frequency (KMP) //2013-05-13-19.12 #include <stdio.h> #include <string.h> const int maxn = 1000006; char a[maxn]; char b[maxn]; int f[maxn]; void getfail() { int l = strlen(b); f[0] = 0; f[1] = 0; for (int i = 1; i < l; i++) { int j = f[i]; while (j && b[i] != b[j]) j = f[j]; if (b[i] == b[j]) f[i+1] = j+1; else f[i+1] = 0; } } int kmp() { int ans = 0; int la = strlen(a); int lb = strlen(b); getfail(); int j = 0; for (int i = 0; i < la; i++) { while (j && a[i] != b[j]) j = f[j]; if (b[j] == a[i]) j++; if (j == lb) ans++; } return ans; } int main() { int t; scanf("%d", &t); for (int i = 1; i <= t; i++) { scanf("%s %s", a, b); printf("Case %d: %d\n", i, kmp()); } return 0; }
