QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1142 | #689853 | #9522. A Simple String Problem | Vegetable_Dog | Vegetable_Dog | Success! | 2024-11-06 21:47:51 | 2024-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'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689853 | #9522. A Simple String Problem | Vegetable_Dog | WA | 1028ms | 6684kb | C++14 | 2.3kb | 2024-10-30 18:56:42 | 2024-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;
}