QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1142#689853#9522. A Simple String ProblemVegetable_DogVegetable_DogSuccess!2024-11-06 21:47:512024-11-06 21:47:51

Details

Extra Test:

Wrong Answer
time: 2ms
memory: 4740kb

input:

7
debafbg
hijckac

output:

6

result:

wrong answer 1st lines differ - expected: '0', found: '6'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689853#9522. A Simple String ProblemVegetable_DogWA 1028ms6684kbC++142.3kb2024-10-30 18:56:422024-11-06 21:49:26

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=200005;
int n;
char s[2][N];

const int bs=131;
const int mod=998244353;
int pw[N];
int hs[2][N];
int geths(int x,int l,int r){ return (hs[x][r]-1ll*hs[x][l-1]*pw[r-l+1]%mod+mod)%mod; }

void pre_work(){
	pw[0]=1;
	for(int i=1;i<N;i++)pw[i]=1ll*pw[i-1]*bs%mod;
	for(int i=0;i<2;i++){
		hs[i][0]=s[i][0];
		for(int j=1;j<=n;j++)hs[i][j]=(1ll*hs[i][j-1]*bs+s[i][j])%mod;
	}
}
int getlcp(int x1,int p1,int x2,int p2){
	if(p1<0||p2<0||p1>n||p2>n)return 0;
	int l=1,r=n-max(p1,p2)+1,mid,res=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(geths(x1,p1,p1+mid-1)==geths(x2,p2,p2+mid-1))res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int getlcs(int x1,int p1,int x2,int p2){
	if(p1<0||p2<0||p1>n||p2>n)return 0;
	int l=1,r=min(p1,p2)+1,mid,res=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(geths(x1,p1-mid+1,p1)==geths(x2,p2-mid+1,p2))res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}

int ans=0;
int work1(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[1][i]!=s[1][i+d])continue;
			int rm1=i+d+getlcp(1,i,1,i+d)-1;
			int lm1=i-getlcs(1,i,1,i+d)+1;
			int lm0=lm1-getlcs(0,lm1-1,1,lm1+d-1);
			if(rm1-lm0+1>=d*2){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}
int work2(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[0][i]!=s[1][i+d])continue;
			int lm=getlcs(0,i,1,i+d);
			int rm=getlcp(0,i,1,i+d);
			if(lm+rm-1>=d){
				flag=1;
				break;
			}
			int t1=getlcs(0,i-lm,0,i+d-lm);
			int t2=getlcp(1,i+rm,1,i+d+rm);
			if(lm+rm-1+t1+t2>=d){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}
int work3(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[0][i]!=s[0][i+d])continue;
			int lm0=i-getlcs(0,i,0,i+d)+1;
			int rm0=i+d+getlcp(0,i,0,i+d)-1;
			int rm1=rm0+getlcp(1,rm0+1,0,rm0-d+1);
			if(rm1-lm0+1>=d*2){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}

int main(){
	scanf("%d",&n);
	scanf("%s%s",s[0],s[1]+1);
	s[0][n]='$'; s[1][0]='#';
	pre_work();
	ans=max(ans,work1());
	ans=max(ans,work2());
	ans=max(ans,work3());
	printf("%d",ans);
	return 0;
}