oj.uz

Submission #716687

# Submission time Handle Problem Language Result Execution time Memory
716687 2023-03-30T19:25:44 Z amirhoseinfar1385 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 56 ms 106676 KB 
#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);
		kmp[0]=-1;
		for(int j=1;j<(int)fake.size();j++){
			int now=kmp[j-1];
			//int cnt=0;
			while(now>=0){
				//cnt++;
				if(fake[j]==fake[now]){
					break;
				}
				if(now==0){
					now=-1;
					break;
				}
				now=kmp[now-1];
			}
			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<maxn;i++){
		for(int j=0;j<maxn;j++){
			maxa[i][j]=0;
		}
	}
	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();
	//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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 106612 KB Output is correct
2 Correct 55 ms 106676 KB Output is correct
3 Incorrect 54 ms 106560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 106612 KB Output is correct
2 Correct 55 ms 106676 KB Output is correct
3 Incorrect 54 ms 106560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 106612 KB Output is correct
2 Correct 55 ms 106676 KB Output is correct
3 Incorrect 54 ms 106560 KB Output isn't correct
4 Halted 0 ms 0 KB -