蒟蒻爆了很久的零了,求大佬帮调。
题目:there
代码:
#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int nex[maxn];
int Getnext(string t) {
int j=0,k=-1,num=0;
nex[j] = k;
while(j<(t.length()-1)) {
if(k==-1||t[j]==t[k]){
j++;
k++;
nex[j]=k;
num++;
} else k=nex[k];
}
return nex[num];
}
void kmp(string text,string key) {
int num=0,cnt=0;
int nextt=Getnext(key);
int i=0,j=0,thenext=text.length(),keylen=key.length();
while (i<=thenext-keylen){
if (j==-1||text[i+j]==key[j]) ++j;
else{
i+=j-nex[j];
j=nex[j];
num++;
}
if (j==keylen){
cout<<num+j<<" ";
cnt++;
}
}
if(cnt==0) cout<<0;
}
int main(){
int n;
string b;
scanf("%d",&n);
cin>>b;
for(int i=1;i<=n;i++){
string a;
cin>>a;
kmp(a,b);
cout<<'\n';
}
return 0;
}
直接套的模板,但是错了,我太弱了