自动搬运

查看原文

来自洛谷，原作者为

	Rain_cyl 热爱阳光的幽灵

搬运于2025-08-24 21:58:59，当前版本为作者最后更新于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;
}