Bzoj4755 [jsoi2016]扭动的回文串

思路简单,细节容易写挂

Posted by yjjr's blog on February 16, 2018

标签: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定义一个“扭动的回文串”为如下情况中的一个:

  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

Hint

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

.BC..

..ECB

题意

给定两个字符串,求它们的最长扭动回文串

定义一个“扭动的回文串”为如下情况中的一个:

  1. A中的一个回文串;

  2. B中的一个回文串;

  3. 或者某一个回文的扭动字符串S(i,j,k)

分析

前两种情况很好求,不多说

对于第三种情况,枚举这个扭动字符串S的回文中心x

如果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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr