【BZOJ4755】扭动的回文串(Manacher,哈希)

时间:2023-01-18 19:38:57

【BZOJ4755】扭动的回文串(Manacher,哈希)

题面

BZOJ

题解

不要真的以为看见了回文串就是\(PAM,Manacher\)一类就可以过。

这题显然不行啊。

我们主要考虑如何解决跨串拼接的回文串。

我们直接枚举回文中心,

即使要跨串,在最优情况下,也一定包含了这个回文中心的最长回文串

那么二分+哈希即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ull unsigned long long
#define MAX 222222
const int base=2333;
int n,ans;
char A[MAX],B[MAX],C[MAX];
ull Hash[2][MAX],pw[MAX<<1];
int f[2][MAX];
void Manacher(char *s,int *p)
{
int mx=0,id=0;
s[0]='>';
for(int i=1;i<=n;++i)
{
p[i]=mx>i?min(p[2*id-i],mx-i):0;
while(s[i-p[i]-1]==s[i+p[i]+1])++p[i];
if(i+p[i]>mx)mx=i+p[i],id=i;
}
}
ull Calc(int c,int l,int r)
{
if(!c)return Hash[0][r]-Hash[0][l-1]*pw[r-l+1];
return Hash[1][l]-Hash[1][r+1]*pw[r-l+1];
}
int Binary(int L,int R)
{
int l=1,r=min(L,n-R+1),ret=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(Calc(0,L-mid+1,L)==Calc(1,R,R+mid-1))ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
int main()
{
scanf("%d",&n);scanf("%s",A+1);scanf("%s",B+1);pw[0]=1;
for(int i=1;i<=n;++i)pw[i]=pw[i-1]*base;
for(int i=1;i<=n;++i)Hash[0][i]=Hash[0][i-1]*base+A[i];
for(int i=n;i>=1;--i)Hash[1][i]=Hash[1][i+1]*base+B[i];
for(int i=1;i<=n;++i)C[i]=A[i];
for(int i=1,j=0;i<=n;++i)A[++j]='*',A[++j]=C[i];A[n+n+1]='*';
for(int i=1;i<=n;++i)C[i]=B[i];
for(int i=1,j=0;i<=n;++i)B[++j]='*',B[++j]=C[i];B[n+n+1]='*';
n=n+n+1;Manacher(A,f[0]);Manacher(B,f[1]);
for(int i=1;i<=n;++i)
{
int L=(i-f[0][i]+1)/2,R=(i+f[0][i])/2;
ans=max(ans,f[0][i]+Binary(L-1,R)*2);
}
for(int i=1;i<=n;++i)
{
int L=(i-f[1][i]+1)/2,R=(i+f[1][i])/2;
ans=max(ans,f[1][i]+Binary(L,R+1)*2);
}
printf("%d\n",ans);
return 0;
}