对本题 #5测试点存在疑问。
查看原帖
对本题 #5测试点存在疑问。
475509
zzl340楼主2022/3/10 22:30

虽然AC了 但是本地测试 #5测试点,无论如何 都是11 163 ,但是#5的输出文件内容 是31 163 ,不知道怎么#5 过的 QWQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);

const int inf = 0x3f3f3f3f;

const int N = 40000;

int ne[N],cnt;

void  getnext(string s){
	int n = s.size();
	int j = -1,i=0;
	ne[i] = j;
	while(i<n){
		if( j == -1 || s[i]==s[j])i++,j++,ne[i] = j;
		else j = ne[j];
		
	} 
}

void kmp(string s,string t){
	int ans = 0,i=0,j=0;
	int idx = 0;
	int m = s.size(),n = t.size();
	while(i < n && j < m){
		if(j<0 || t[i] == s[j])i++,j++;
		else j = ne[j];
		if(j==m){
			ans++;
			if(ans==1){
				idx = i-m;
			}
			j=0;
			i--; 
		}
	}
	if(ans)cout<<ans<<" "<<idx;
	else cout<<-1<<endl;
}

int main(){
	string s,t;
	
	cin>>s;
	getchar();
	getline(std::cin,t);
	int m = s.size(),n = t.size();
	 
	for(int i=0;i<m;i++){
		if(s[i]>='a' && s[i]<='z'){
			s[i] = s[i]-'a'+'A';
		}
	}
	for(int i=0;i<n;i++){
		if(t[i]>='a' && t[i]<='z'){
			t[i] = t[i]-'a'+'A';
		}
	}
	
	t = ' ' + t + ' ';
	s = ' ' + s + ' ';
	
	getnext(s);
	
	kmp(s,t);
	
	return 0;
}

2022/3/10 22:30
加载中...