WA求助qwq
查看原帖
WA求助qwq
552088
12468C楼主2022/7/19 11:25
#include<bits/stdc++.h>
using namespace std;
string s,t;
const int maxn=1001;
int ans[maxn];
void get_ans(string t){
	int j=0,k=-1;
	ans[0]=-1;
	while(j<t.length()){
		if(k==-1||t[j]==t[k]){
			j++,k++;
			if(j<t.length()&&t[j]==t[k]){
				ans[j]=ans[k];
			}
			else{
				ans[j]=k;
			}
		}
		else{
			k=ans[k];
		}
	}
}
void KMP(string s,string t,int a){
	int i=a,j=0,sum=0;
	get_ans(t);
	while(i<s.length()&&j<t.length()){
		sum++;
		if(j==-1||s[i]==t[j]){
			i++,j++;
		} 
		else{
			j=ans[j];
		}
		if(j==t.length()){
		    cout<<i-t.length()+1<<endl;
	    	j=ans[j];
    	}
	}	
}
int main(){
	cin>>s>>t;
	KMP(s,t,0);
	for(int i=1;i<=t.length();i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
2022/7/19 11:25
加载中...