\(manacher\)+二分+双哈希

看见标题就不想做的童鞋可以看下面，让你更绝望。

这题思路比较简单明了，我们就按照题目说的那样，设串\(T\)为答案，分两种情况讨论：

1. 当\(T\)是\(A\)串或\(B\)串中的一个回文串时，我们可以直接用\(manacher\)求得答案。

2. 当\(T\)是某一个回文的扭动字符串\(S(i,j,k)\)时，我们可以枚举这个串\(T\)的中点\(i\)是在\(A\)串还是在\(B\)串，然后解法如下：

假设我们现在枚举\(i\)是在\(A\)串，我们有这么一个结论：

\(T\)的长度至少是以\(i\)为中点在\(A\)串中的最长回文串的长度，即\(hwA[i]-1\)。

也就是说，\(T\)中肯定包含\(A[i-hwA[i]+1...i+hwA[i]-1]\)。

然后因为\(A[i-hwA[i]]!=A[i+hwA[i]]\)，所以我们可以直接从\(A[i-hwA[i]]\)和\(B[i+hwA[i]-1]\)开始枚举就行了。

也就是说，这个扭动字符串\(S(i,j,k)\)的\(j\)就是\(i+hwA[i]-1\)了。

至于之后的枚举，直接枚举会比较麻烦，我们可以二分长度，用前缀和板双哈希来判断。

最后的代码如下：

#include
    
       #define N 200010#define p1 100007#define p2 233333#define limit 27  using namespace std;  int len,ans,ra[N],rb[N],standard[2][N],suma[2][N],sumb[2][N];char a[N],b[N];  void init()//现在字符串中插入'#'{    for(int i=len;i>=0;i--)    {        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]='%',standard[0][0]=standard[1][0]=1;}  void manacher(char *s,int *radius)//manacher{    int maxright=0,mid;    for(int i=1;i<=len;i++)    {        if(i
     
      <<1)-i],maxright-i+1);        else radius[i]=1;        while(s[i-radius[i]]==s[i+radius[i]])radius[i]++;        if(i+radius[i]-1>maxright)        {            maxright=i+radius[i]-1;            mid=i;        }    }} void gethash()//双哈希预处理{    for(int i=1;i<=len;i++)//计算类似于进制基本单位的东东    {        ans=max(ans,max(ra[i],rb[i]));//顺便统计答案        standard[0][i]=(long long)standard[0][i-1]*limit%p1;        standard[1][i]=(long long)standard[1][i-1]*limit%p2;    }    for(int i=2;i
      
       >1]=((long long)suma[0][(i>>1)-1]*limit+a[i])%p1;        suma[1][i>>1]=((long long)suma[1][(i>>1)-1]*limit+a[i])%p2;    }    for(int i=len-1;i>=1;i-=2)    {        sumb[0][i>>1]=((long long)sumb[0][(i>>1)+1]*limit+b[i])%p1;        sumb[1][i>>1]=((long long)sumb[1][(i>>1)+1]*limit+b[i])%p2;    }} bool check(int l1,int r1,int l2,int r2,int l)//双哈希检验{    int x=(suma[0][r1]-(long long)suma[0][l1-1]*standard[0][l]%p1)%p1;    int y=(sumb[0][l2]-(long long)sumb[0][r2+1]*standard[0][l]%p1)%p1;    x=(x+p1)%p1,y=(y+p1)%p1;    if (x!=y)return false;//第一层哈希    x=(suma[1][r1]-(long long)suma[1][l1-1]*standard[1][l]%p2)%p2;    y=(sumb[1][l2]-(long long)sumb[1][r2+1]*standard[1][l]%p2)%p2;    x=(x+p2)%p2;y=(y+p2)%p2;    return x==y;//第二层哈希} int solve(int x,int y)//二分{    int l=0,r=min(x,(len>>1)-y+1),ans=0;    while(l<=r)    {        int mid=(l+r)>>1;        if(check(x-mid+1,x,y,y+mid-1,mid))l=mid+1,ans=mid;        else r=mid-1;    }    return ans;} void query()//枚举T的中点{    for(int i=2;i
       
        >1,r>>=1;        ans=max(ans,ra[i]+solve(l-1,r)*2);    }    for(int i=2;i
        
         >1,r>>=1;        ans=max(ans,rb[i]+solve(l,r+1)*2);    }}  int main(){    scanf("%d%s%s",&len,a+1,b+1);    init();    manacher(a,ra);manacher(b,rb);    for(int i=1;i<=len;i++)ra[i]--,rb[i]--;//计算回文长度    gethash();    query();    printf("%d\n",ans);    return 0;}