Submission #716710

#	Time	Username	Problem	Language	Result	Execution time	Memory
716710		amirhoseinfar1385	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	2 ms	340 KiB

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-kmp[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: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40