题目链接: https://vjudge.net/contest/70325#problem/B
题意: 输出模式串在主串中出现的次数
思路: kmp模板
在 kmp 函数中匹配成功计数加一, 再令 j = nxt[j] 即可.
感觉有点奇怪的就是我拿 A 题的模板写这题居然会 tle, 而拿这题的模板写 A 题又没有 A 题的模板跑的快...可能是数据特殊吧:) .
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std; const int MAXN = 1e6 + ;
char a[MAXN], b[MAXN];
int nxt[MAXN], n, m; void get_nxt(void){
memset(nxt, , sizeof(nxt));
int j = -, i = ;
nxt[] = -;
while(i < m){
if(j == - || b[j] == b[i]){
nxt[i + ] = j + ;
i++;
j++;
}else j = nxt[j];
}
} int kmp(void){
get_nxt();
int i = , j = , ans = ;
while(i < n && j < m){
if(j == - || a[i] == b[j]){
i++;
j++;
}else j = nxt[j];
if(j == m){
ans++;
j = nxt[j];
}
}
return ans;
} int main(void){
int t;
scanf("%d", &t);
while(t--){
scanf("%s%s", b, a);
n = strlen(a);
m = strlen(b);
printf("%d\n", kmp());
}
return ;
}