独立的A,B串很好处理,套上一个Manacher就可以了。
对于扭动的回文串,其实有一个结论:
对于回文中心为$i$的扭动回文串,假设它的最长范围为$[l,r]$,
那么它一定存在一种构造方案由原有的$A$串或$B$串以$i$为回文中心的回文字串拓展而来。
证明不难,可以独立完成,大概思路就是反证法,证明其是等价的。
之后就可以二分判定拓展区间了,哈希判断是否可行。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline
#define eps 1e-8
using namespace std;
const int N=1e5+5;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
char s[N<<1];int f[N<<1],g[N<<1],n,m;
ull s1[2][N],s2[2][N],P[2][N];
I void Manacher(char *a,int *p)
{
for(int i=1,j;i<=n;i++)s[j=2*i-1]='#',s[j+1]=a[i];
int pos=0,r=0;m=2*n+1;s[m]='#';
for(int i=1,j;i<=m;i++)
{
j=2*pos-i;if(i<r)p[i]=min(p[j],r-i);
else p[i]=1;for(;i-p[i]>=1&&i+p[i]<=m&&s[i-p[i]]==s[i+p[i]];++p[i]);
if(i+p[i]>r)r=i+p[i],pos=i;
}
for(int i=1;i<=m;i++)p[i]--;
}
char a[N],b[N];
I bool check(int r1,int l2,int len)
{
int l1=r1-len+1,r2=l2+len-1;
ull w1,w2;
w1=s1[0][r1]-s1[0][l1-1]*P[0][len];
w2=s2[0][l2]-s2[0][r2+1]*P[0][len];
if(w1!=w2)return 0;
w1=s1[1][r1]-s1[1][l1-1]*P[1][len];
w2=s2[1][l2]-s2[1][r2+1]*P[1][len];
return w1==w2;
}
int calc(int j,int k)
{
int l=0,r=min(j,n-k+1);
while(l<r)
{
int mid=l+r+1>>1;
if(check(j,k,mid))l=mid;
else r=mid-1;
}
return l;
}
void solve()
{
qr(n);scanf("%s%s",a+1,b+1);int ans=0;
P[0][0]=P[1][0]=1;for(int i=1;i<=n;i++)P[0][i]=P[0][i-1]*p0,P[1][i]=P[1][i-1]*p1;
Manacher(a,f);
for(int i=1;i<=n;i++)
s1[0][i]=s1[0][i-1]*p0+(a[i]-'A'+1),
s1[1][i]=s1[1][i-1]*p1+(a[i]-'A'+1);
for(int i=1;i<=m;i++)
ans=max(ans,f[i]);
Manacher(b,g);
for(int i=n;i>=1;i--)
s2[0][i]=s2[0][i+1]*p0+(b[i]-'A'+1),
s2[1][i]=s2[1][i+1]*p1+(b[i]-'A'+1);
for(int i=1;i<=m;i++)
ans=max(ans,g[i]);
for(int i=2;i<m;i++)
{
int l=i-f[i],r=i+f[i];
l=(l+1)/2,r=r/2;
ans=max(ans,f[i]+calc(l-1,r)*2);
}
for(int i=2;i<m;i++)
{
int l=i-g[i],r=i+g[i];
l=(l+1)/2,r=r/2;
ans=max(ans,g[i]+calc(l,r+1)*2);
}
qw(ans);puts("");
}
int main()
{
solve();
return 0;
}
最后一次更新于2020-05-19
0 条评论