版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Charles_Zaqdt/article/details/102543718
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2087
写法就是一个裸的KMP,只不过是每次再匹配了一次以后,让j=0(让其从第一个开始匹配)
AC代码:
#include <bits/stdc++.h>
#define maxn 1005
#define ll long long
using namespace std;
string s, p;
int Next[maxn];
int ans;
void init(){
int j = 0, k = -1;
int len = p.length();
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 = s.length();
int l2 = p.length();
while(i < l1){
if(j == -1 || s[i] == p[j]){
i ++;
j ++;
}
else{
j = Next[j];
}
if(j == l2){
j = 0;
ans ++;
}
}
}
int main()
{
while(cin>>s){
if(s == "#") break;
cin>>p;
init();
ans = 0;
kmp();
printf("%d\n", ans);
}
return 0;
}