题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1686
题意是输入一个模式串p,再输入一个文本串s,问p在s中出现了多少次。
KMP的裸题
AC代码:
#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
char s[maxn], p[10005];
int Next[10005];
int T, ans;
void init(){
int j = 0, k = -1;
int len = strlen(p);
memset(Next, -1, sizeof(Next));
while(j < len){
if( k == -1 || p[j] == p[k]){
k ++;
j ++;
Next[j] = k;
}
else k = Next[k];
}
}
void kmp(){
int i = 0, j = 0;
int l1 = strlen(p);
int l2 = strlen(s);
while(j < l2){
if(i == -1 || p[i] == s[j]){
i ++;
j ++;
}
else{
i = Next[i];
}
if(i == l1){
i = Next[i];
ans ++;
}
}
}
int main()
{
scanf("%d", &T);
while(T--){
scanf("%s%s", p, s);
init();
ans = 0;
kmp();
printf("%d\n", ans);
}
return 0;
}