标签：Manacher，hash，二分
题目
Description
JYY有两个长度均为N的字符串A和B。
一个“扭动字符串S(i,j,k)由A中的第i个字符到第j个字符组成的子串与B中的第j个字符到第k个字符组成的子串拼接而成。
比如，若A=’XYZ’，B=’UVW’，则扭动字符串S(1,2,3)=’XYVW’。
JYY定义一个“扭动的回文串”为如下情况中的一个：
-
A中的一个回文串；
-
B中的一个回文串；
-
或者某一个回文的扭动字符串S(i,j,k)
现在JYY希望找出最长的扭动回文串。
Input
第一行包含一个正整数N。
第二行包含一个长度为N的由大写字母组成的字符串A。
第三行包含一个长度为N的由大写字母组成的字符串B。
1≤N≤10^5。
Output
输出的第一行一个整数，表示最长的扭动回文串。
Sample Input
5
ABCDE
BAECB
Sample Output
5
Hint
最佳方案中的扭动回文串如下所示（不在回文串中的字符用.表示）：
.BC..
..ECB
题意
给定两个字符串，求它们的最长扭动回文串
定义一个“扭动的回文串”为如下情况中的一个：
-
A中的一个回文串；
-
B中的一个回文串；
-
或者某一个回文的扭动字符串S(i,j,k)
分析
前两种情况很好求，不多说
对于第三种情况，枚举这个扭动字符串S的回文中心ｘ
如果x位于A中，那么A能取到的左边界为1->x-pa[x]-1，B能取到的右边界为x+pb[x]->len
位于B中同理
下面可以二分长度判断A的一部分是否和B的一样，判断的过程用hash+前后缀和
常数太丑接近垫底了
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6,limit=17,p1=1e5+7,p2=1e5+9;
char a[maxn<<1],b[maxn<<1];
int pa[maxn<<1],pb[maxn<<1],sa[2][maxn<<1],sb[2][maxn<<1],g[2][maxn<<1],len,ans;
void Manacher(char *ch,int *p){
int Max=0,id;
rep(i,1,len){
if(Max>i)p[i]=min(Max-i,p[2*id-i]);else p[i]=1;
while(ch[i+p[i]]==ch[i-p[i]])p[i]++;
if(Max<p[i]+i)Max=p[id=i]+i;
}
}
inline bool check(int l1,int r1,int l2,int r2,int Len){
int x=(sa[0][r1]-1ll*sa[0][l1-1]*g[0][Len]%p1)%p1;
int y=(sb[0][l2]-1ll*sb[0][r2+1]*g[0][Len]%p1)%p1;
x=(x+p1)%p1,y=(y+p1)%p1;
if(x!=y)return 0;
x=(sa[1][r1]-1ll*sa[1][l1-1]*g[1][Len]%p2)%p2;
y=(sb[1][l2]-1ll*sb[1][r2+1]*g[1][Len]%p2)%p2;
x=(x+p2)%p2,y=(y+p2)%p2;
return x==y;
}
inline int solve(int L,int R){
int l=0,r=min(L,(len>>1)-R+1),ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(L-mid+1,L,R,R+mid-1,mid))l=mid+1,ans=mid;else r=mid-1;
}
return ans;
}
int main(){
len=read();
scanf("%s%s",a+1,b+1);
dep(i,len,1)a[i<<1]=a[i],b[i<<1]=b[i],a[i<<1|1]=b[i<<1|1]='&';
len=len<<1|1;a[0]=b[0]='#',a[1]=b[1]='&',a[len+1]=b[len+1]='^',g[0][0]=g[1][0]=1;
Manacher(a,pa),Manacher(b,pb);rep(i,1,len)pa[i]--,pb[i]--;
rep(i,1,len){
ans=max(ans,max(pa[i],pb[i]));
g[0][i]=1ll*g[0][i-1]*limit%p1;
g[1][i]=1ll*g[1][i-1]*limit%p2;
}
for(int i=2;i<len;i+=2){
sa[0][i>>1]=(1ll*sa[0][(i>>1)-1]*limit+a[i])%p1;
sa[1][i>>1]=(1ll*sa[1][(i>>1)-1]*limit+a[i])%p2;
}
for(int i=len-1;i>1;i-=2){
sb[0][i>>1]=(1ll*sb[0][(i>>1)+1]*limit+b[i])%p1;
sb[1][i>>1]=(1ll*sb[1][(i>>1)+1]*limit+b[i])%p2;
}
rep(i,2,len-1){
int l=i-pa[i],r=i+pa[i];
l=(l+1)>>1,r>>=1;
ans=max(ans,pa[i]+solve(l-1,r)*2);
}
rep(i,2,len-1){
int l=i-pb[i],r=i+pb[i];
l=(l+1)>>1,r>>=1;
ans=max(ans,pb[i]+solve(l,r+1)*2);
}
cout<<ans<<endl;
return 0;
}
