原题描述
输入
第一行一个整数N，表示测试数据组数。
接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。
其中N<=20
输出
对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。
样例输入
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
样例输出
3
1
3
1
0
KMP算法
KMP算法是单模式串的字符匹配算法，如果需要进行多模式串的字符匹配，则需要用到AC自动机算法。
详细的KMP算法可以查看CSDN博客
整个求解的思路可以如下：
- 求解Next数组
- 进行字符串匹配
求解Next数组的过程：
- next[0] = next[1] = 0
- 从i=1处开始遍历模式串p，初始j=next[i]
- 循环检测 j>0&&p[j]!=p[i]，执行j=next[j] ，直到循环退出
- 判断 j和i处模式串的值是否相等，若相等，则j++
- next[i+1] = j ，继续步骤2遍历
字符串匹配的过程：
- 初始化模式串p的遍历j = 0，遍历原字符串s
- 循环检测 j>0&&p[j]!=s[i]，执行j=next[j] ，直到循环退出
- 判断模式串位置j和原串s位置i的值是否相等，若相等，则j++
- 如果j==模式串的长度，则说明匹配成功一次，可以进行后续处理，继续步骤2遍历
C++代码
#include <iostream>
using namespace std;
void compute(string p, int* next) {
int len = p.length();
next[0] = next[1] = 0;
int j = 0;
for (int i = 1; i < len; i++) {
j = next[i];
while (j > 0 && p[j] != p[i]) {
j = next[j];
}
if (p[j] == p[i]) {
j++;
}
next[i+1] = j;
}
}
int match(string s, string p, int* next) {
int j = 0;
int counts = 0;
for (int i = 0; i < s.length(); i++) {
while (j > 0 && s[i] != p[j]) {
j = next[j];
}
if (s[i] == p[j]) {
j++;
}
if (j == p.length()) {
counts++;
j = next[j];
}
}
return counts;
}
int main(void) {
int nums;
string s, p;
int *next;
cin >> nums;
while (nums--) {
cin >> p;
cin >> s;
next = new int[p.length() + 1];
compute(p, next);
cout << match(s, p, next) << endl;
delete next;
}
return 0;
}
Bug Free Procedure 从记事本直接写代码
2016.12.16 Bingo！！！一次性AC
1. 要注意在match函数里面对模式串的j的判断