Submission #716712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
716712	2023-03-30T22:09:55 Z	amirhoseinfar1385	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	432 ms	400 KB

necklace

#include<bits/stdc++.h>
using namespace std;
string s,ss;
int n,m;
const int maxn=3000+10;
int lcp[maxn],fkmp[maxn],revfkmp[maxn];
string fake;
vector<int>kmp;

void findkmp(int mid){
	for(int i=0;i<maxn;i++){
		revfkmp[i]=fkmp[i]=0;
	}
	fake.clear();
	for(int i=mid;i<n;i++){
		fake.push_back(s[i]);
	}
	fake.push_back('$');
	int len=fake.size();
	fake+=ss;
	kmp.clear();
	kmp.resize((int)fake.size()+10);
	for(int i=1;i<(int)fake.size();i++){
		int now=kmp[i-1];
		while(now>=0){
			if(fake[i]==fake[now]){
				break;
			}
			if(now==0){
				now=-1;
				break;
			}
			now=kmp[now-1];
		}
		now++;
		kmp[i]=now;
		if(i>=len){
			fkmp[i-len]=now;
		}
	}
	fake.clear();
	for(int i=mid-1;i>=0;i--){
		fake.push_back(s[i]);
	}
	fake.push_back('$');
	len=fake.size();
	reverse(ss.begin(),ss.end());
	fake+=ss;
	reverse(ss.begin(),ss.end());
	kmp.clear();
	kmp.resize((int)fake.size()+10);
	for(int i=1;i<(int)fake.size();i++){
		int now=kmp[i-1];
		while(now>=0){
			if(fake[now]==fake[i]){
				break;
			}
			if(now==0){
				now=-1;
				break;
			}
			now=kmp[now-1];
		}
		now++;
		kmp[i]=now;
		if(i>=len){
			revfkmp[m-1-(i-len)]=now;
		}
	}

}

pair<int,pair<int,int>> solve(){
	n=s.size(),m=ss.size();
	pair<int,pair<int,int>>res;
	for(int i=0;i<maxn;i++){
		lcp[i]=0;
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<m;j++){
			if(s[i]==ss[j]){
				lcp[j]=lcp[j+1]+1;
			}
			else{
				lcp[j]=0;
			}
			//cout<<i<<" "<<j<<" "<<lcp[j]<<"\n";
			if(res.first<lcp[j]){
				res=make_pair(lcp[j],make_pair(i,j));
			}
		}
	}
	for(int i=1;i<n;i++){
		findkmp(i);
		for(int h=1;h<m;h++){
//			if(i==3){
//				cout<<h<<" "<<fkmp[h-1]<<" "<<revfkmp[h]<<"\n";
//			}
			if(fkmp[h-1]+revfkmp[h]>res.first){
				//cout<<"wtf "<<fkmp[h-1]<<" "<<revfkmp[h]<<" "<<fkmp[h-1]+revfkmp[h]<<" "<<i<<" "<<h<<"\n";
				res=make_pair(fkmp[h-1]+revfkmp[h],make_pair(i-revfkmp[h],h-fkmp[h-1]));
			}
		}
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s>>ss;
	auto res=solve();
	reverse(ss.begin(),ss.end());
	auto res2=solve();
	//cout<<res2.second.second<<"\n";
	if(res2.first>res.first){
		swap(res2,res);
		res.second.second=m-(res.second.second+res.first-1)-1;
	}
	cout<<res.first<<"\n";
	cout<<res.second.first<<" "<<res.second.second<<"\n";
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	380 KB	Output is correct
2	Correct	355 ms	400 KB	Output is correct
3	Correct	432 ms	388 KB	Output is correct
4	Correct	348 ms	392 KB	Output is correct
5	Correct	308 ms	388 KB	Output is correct
6	Correct	336 ms	384 KB	Output is correct
7	Correct	360 ms	384 KB	Output is correct
8	Correct	390 ms	340 KB	Output is correct
9	Correct	375 ms	396 KB	Output is correct