题解：P4324 [JSOI2016] 扭动的回文串

Rain_cyl · 2024-11-11 13:53:40 · 题解

前两种情况直接哈希+二分。

对于第三种情况，只需在确定中心点后，先在原本的串上找到最长的回文串，再分别到 sa 和 sb 上扩展。

可以证明这是最优的，因为如果你从原本串上非最长的回文串开始扩展，那如果要达到原来的长度，就需要 sa 和 sb 有更长的一段是回文的，显然不优。

例如：

那若 sa 的 \texttt{C} 为中心点，选最长的 \texttt{ABCBA} 开始扩展，可以得到 \texttt{DE} 和 \texttt{ED} 是回文的;

而如果从 \texttt{BCB} 开始扩展，要达到原来长度，就要求 \texttt{DEA} 和 \texttt{WED} 回文，但并非回文，因此不优。

时间复杂度 O(n\log n)。

目前题解中长度最短的代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+5,P=13331;

int n;
char sa[N],sb[N];
ULL p[N],ha[N],rha[N],hb[N],rhb[N];

int getH(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

int getlen(ULL h[],ULL rh[],int ll,int rr){ //正着的是h，从ll往左，反着的是rh，从rr往右
    int l=0,r=min(ll,n-rr+1);
    while(l<r){
        int mid=l+r+1>>1;
        if(getH(h,ll-mid+1,ll)==getH(rh,n-rr-mid+2,n-rr+1)) l=mid;
        else r=mid-1;
    }
    return l;
}

int main(){
    scanf("%d%s%s",&n,sa+1,sb+1);
    p[0]=1;
    for(int i=1; i<=n; i++){
        p[i]=p[i-1]*P;
        ha[i]=ha[i-1]*P+sa[i];
        hb[i]=hb[i-1]*P+sb[i];
    }
    for(int i=n; i; i--){
        rha[n-i+1]=rha[n-i]*P+sa[i];
        rhb[n-i+1]=rhb[n-i]*P+sb[i];
    }

    int res=1;
    for(int i=2; i<n; i++){ //回文串长为奇数
        int la=getlen(ha,rha,i,i),lb=getlen(hb,rhb,i,i);
        res=max(res,la*2-1+getlen(ha,rhb,i-la,i+la-1)*2);
        res=max(res,lb*2-1+getlen(ha,rhb,i-lb+1,i+lb)*2);
    }
    for(int i=1; i<n; i++){ //回文串长为偶数
        int la=getlen(ha,rha,i,i+1),lb=getlen(hb,rhb,i,i+1);
        res=max(res,la*2+getlen(ha,rhb,i-la,i+la)*2);
        res=max(res,lb*2+getlen(ha,rhb,i-lb+1,i+lb+1)*2);
    }

    printf("%d",res);
    return 0;
}