目录

Oulipo (KMP 统计出现次数) 题目题解及思路

Oulipo (KMP 统计出现次数)

题目

求模式串在待匹配串中的出现次数。Input 第一行是一个数字T，表明测试数据组数。之后每组数据都有两行： 第一行为模式串，长度不大于10,000； 第二行为待匹配串，长度不大于1,000,000。（所有字符串只由大写字母组成）Output 每组数据输出一行结果。Sample Input 4 ABCD ABCD SOS SOSOSOS CDCDCDC CDC KMP SOEASYSample Output 1 3 0 0

题解及思路

就是直接KMP然后求出现次数。

注意的地方：

next 数组的范围，也就是循环结束的地方。可能会模式串是一位的情况。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char str[1000005]; char pi[10005]; int nex[10005]; int m, n; void getNext(char *p, int *ne) { ne[0] = -1; int i = -1, j = 0; while (j < n) //注意循环的范围，之前错在 j<n-1 { if (i == -1 || p[i] == p[j]) { if (p[i + 1] == p[j + 1]) ne[++j] = ne[++i]; else ne[++j] = ++i; } else i = ne[i]; } } int kmpSearch() { int j = 0, k = 0, res = 0; //j p; while (k < m && j < n) { if (j == -1 || str[k] == pi[j]) k++, j++; else j = nex[j]; if (j == n) { res++; j = nex[j];//这里也应当注意。当模式串只有一位且等于 //主串某位的时候会死循环不加这行会 } } return res; } int main() { int T; cin >> T; while (T--) { scanf("%s", pi); scanf("%s", str); n = strlen(pi); m = strlen(str); getNext(pi, nex); cout << kmpSearch() << endl; } }

转载于:https://www.cnblogs.com/tttfu/p/11295468.html

相关资源：JAVA上百实例源码以及开源项目