中文题。题目链接:https://loj.ac/problem/10043
这题代码和 HDU2087 的一样,但是注意,该AC代码在这两个题目的样例都能过,但是这两题的输入不一样!!!
不要直接交!!!改输入就行!!!
该题是KMP的模板略微变形的题目。
KMP的模板是求子串在原串中出现了几次,
本题是可以间接看作是子串不重叠的在原串中出现了几次。
所以我们只需要加两行代码,即在 kmp() 函数中加入:
if(j==lens)
j=0,cnt++; //(j=0 因为题目规定的是不能重叠,也就相当于已经找到的位置不允许再次使用!)
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int N=1010;
int lens,lent,nex[N];
char s[N],t[N];
void getnex()
{
int i=0,j=-1;
nex[0]=-1;
while(i<lens)
{
if(j==-1||s[i]==s[j])
nex[++i]=++j;
else
j=nex[j];
}
}
int kmp()
{
int i=0,j=0,cnt=0;
while(i<lent)
{
if(j==-1||t[i]==s[j]) // if j<0
i++,j++;
else
j=nex[j];
if(j==lens)
j=0,cnt++;
}
return cnt;
}
int main()
{
while(cin>>t)
{
lent=strlen(t);
if(lent==1&&t[0]=='#')
break;
cin>>s;
lens=strlen(s);
getnex();
cout<<kmp()<<endl;
}
return 0;
}