首页 > 代码库 > [BZOJ]4755: [Jsoi2016]扭动的回文串

[BZOJ]4755: [Jsoi2016]扭动的回文串

Time Limit: 10 Sec  Memory Limit: 512 MB

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定义一个“扭动的回文串”为如下情况中的一个:
  1.A中的一个回文串;
  2.B中的一个回文串;
  3.或者某一个回文的扭动字符串S(i,j,k)
  现在JYY希望找出最长的扭动回文串。

Input

  第一行包含一个正整数N。
  第二行包含一个长度为N的由大写字母组成的字符串A。
  第三行包含一个长度为N的由大写字母组成的字符串B。
  1≤N≤10^5。

Output

  输出的第一行一个整数,表示最长的扭动回文串。

Sample Input

  5
  ABCDE
  BAECB

Sample Output

  5
  最佳方案中的扭动回文串如下所示(不在回文串中的字符用.表示):
  .BC..
  ..ECB

Solution

  一个扭动回文串可以拆成3个部分,第一部分在A,第二部分是A或B的一个回文子串,第三部分在B,其中第一部分翻转后和第三部分相同,并且肯定存在一个最优解,它的第二部分是它回文中心向外延伸得到的最长的回文串,对A和B分别跑manacher找到各个回文中心的最长回文半径后二分+hash即可。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define MN 100000
#define X 31
#define MOD 998244353
char a[MN+5],b[MN+5],s[MN*2+5];
int n,p[MN+5],ha[MN+5],hb[MN+5],d[MN*2+5],ans;
void solve(char*S)
{
    int i,mx=0,L,R,l,r,mid,res;
    for(s[0]=.,i=1;i<2*n;++i)s[i]=i&1?S[i+1>>1]:#;
    for(i=1;i<2*n;++i)
    {
        d[i]=mx+d[mx]<i?0:min(d[2*mx-i],mx+d[mx]-i);
        while(s[i+d[i]+1]==s[i-d[i]-1])++d[i];
        if(i+d[i]>mx+d[mx])mx=i;
        L=i-d[i]+2>>1;R=i+d[i]+1>>1;
        if(S==a)--R;else ++L;
        for(l=0,r=min(L-1,n-R);l<=r;)
        {
            mid=l+r>>1;
            if((1LL*(ha[L-1]-1LL*ha[L-mid-1]*p[mid])%MOD+MOD)%MOD==
               (1LL*(hb[R+1]-1LL*hb[R+mid+1]*p[mid])%MOD+MOD)%MOD)res=mid,l=mid+1;
            else r=mid-1;
        }
        ans=max(ans,R-L+2+res*2);
    }
}
int main()
{
    int i,mx;
    scanf("%d%s%s",&n,a+1,b+1);
    for(p[0]=i=1;i<=n;++i)p[i]=1LL*p[i-1]*X%MOD;
    for(i=1;i<=n;++i)ha[i]=(1LL*ha[i-1]*X+a[i])%MOD;
    for(i=n;i;--i)hb[i]=(1LL*hb[i+1]*X+b[i])%MOD;
    solve(a);solve(b);
    printf("%d",ans);
}

[BZOJ]4755: [Jsoi2016]扭动的回文串