Submission #716673

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

necklace

#include<bits/stdc++.h>
using namespace std;
string s,ss;
const int maxn=3000+10;
int lcp[maxn][maxn],fkmp[maxn][maxn],maxa[maxn][maxn];
int n,m;
void findlcp(){
	for(int i=0;i<maxn;i++){
		for(int j=0;j<maxn;j++){
			lcp[i][j]=0;
		}
	}
	for(int i=n-1;i>=0;i--){
		for(int j=m-1;j>=0;j--){
			if(s[i]==ss[j]){
				lcp[i][j]=lcp[i+1][j+1]+1;
			}
		}
	}
}

void findkmp(){
	for(int i=0;i<maxn;i++){
		for(int j=0;j<maxn;j++){
			fkmp[i][j]=0;
		}
	}
	for(int i=0;i<n;i++){
		string fake;
		for(int j=i;j<n;j++)
		{
			fake.push_back(s[j]);
		}
		fake.push_back('@');
		fake+=ss;
		int len=n-i;
	//	if(i==5){
	//		cout<<fake<<"\n";
	//	}
		vector<int>kmp(fake.size()+10);
		for(int j=1;j<(int)fake.size();j++){
			int now=kmp[j-1];
			while(true){
				if(fake[j]==fake[now]){
					break;
				}
				if(now==0){
					now=-1;
					break;
				}
				now=kmp[now];
			}
			now++;
			kmp[j]=now;
			if(j>len){
				fkmp[i][j-len-1]=now;
			}
		//	cout<<len<<" "<<j<<" "<<kmp[j]<<"\n";
		}
	}
}

void findmaxa(){
	for(int i=0;i<=m;i++){
		maxa[i][0]=fkmp[0][i]+0;
		for(int j=1;j<n;j++){
			maxa[i][j]=max(maxa[i][j-1],fkmp[j][i]+j);
		}
	}
}

pair<int,pair<int,int>> solve(){
	n=s.size(),m=ss.size();
	findlcp();
	findkmp();
	findmaxa();
	//cout<<lcp[3][4]<<" "<<maxa[3][5]<<"\n";
	pair<int,pair<int,int>>res;
	res.first=0;
	res.second=make_pair(0,0);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(lcp[i][j]>=1){
				if(j==0){
					res=max(res,make_pair(lcp[i][j],make_pair(i,j)));
				}
				int lasta=maxa[j-1][i+lcp[i][j]]-1;
		//		if(i==3&&j==4){
		//			cout<<lasta<<"\n";
		//		}
				res=max(res,make_pair(lasta-i+1,make_pair(i,j-1-(lasta-(i+lcp[i][j]-1))+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();
	if(res2.first>res.first){
		swap(res2,res);
		res.second.second=m-res.second.second-1;
	}
	res.second.first++;
	res.second.second++;
	cout<<res.first<<"\n";
	cout<<res.second.first<<" "<<res.second.second<<"\n";
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40