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

对于第三种情况，只需在确定中心点后，先在原本的串上找到最长的回文串，再分别到 $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;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int B=41;
ull h1[100010],t1[100010],h2[100010],t2[100010],pb[100010];
ull qpow(ull a,ll b){
	ull ans=1;
	for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;
	return ans;
} 
int n;
string s1,s2;
bool check(int v){
	for(int i=1;i+v-1<=n;i++){
		if(h1[i+v-1]-h1[i-1]*pb[v]==t1[i]-t1[i+v]*pb[v])return 1;
		if(h2[i+v-1]-h2[i-1]*pb[v]==t2[i]-t2[i+v]*pb[v])return 1;
	}
	v--;
	for(int i=1;i+v-1<=n;i++){
		int x=i,y=i+v-1;
		int l=0,r=(v+1)/2;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(h1[x+mid-1]-h1[x-1]*pb[mid]==t2[y-mid+1]-t2[y+1]*pb[mid])l=mid;
			else r=mid-1;
		} 
		int xx=x+l,yy=y-l;
		if(xx>yy)return 1;
		if(h1[yy+1]-h1[xx-1]*pb[yy-xx+2]==t1[xx]-t1[yy+2]*pb[yy-xx+2])return 1;
		if(h2[yy]-h2[xx-2]*pb[yy-xx+2]==t2[xx-1]-t2[yy+1]*pb[yy-xx+2])return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>s1>>s2;
	pb[0]=1;
	for(int i=1;i<=n;i++){
		pb[i]=pb[i-1]*B;
	}
	s1=" "+s1;
	s2=" "+s2;
	for(int i=1;i<=n;i++){
		h1[i]=h1[i-1]*B+s1[i]-'A';
		h2[i]=h2[i-1]*B+s2[i]-'A';
	}
	for(int i=n;i;i--){
		t1[i]=t1[i+1]*B+s1[i]-'A';
		t2[i]=t2[i+1]*B+s2[i]-'A';
	}
	int ans=0;
	int l=0,r=n/2+1;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid*2+1))l=mid;
		else r=mid-1;
	}
	ans=max(ans,l*2+1);
	l=0,r=n/2+1;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid*2))l=mid;
		else r=mid-1;
	}
	ans=max(ans,l*2);
	cout<<ans;
	return 0;
}```

超级长的代码，好看但不好打，还是去看题解吧。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,B=131,P=1e9+7;
int s1[N],s2[N],fac[N],d1[N],d2[N],e1[N],e2[N];
char st1[N],st2[N];int n;
int get(int l,int r){return ((s1[r]-s1[l-1]*fac[r-l+1])%P+P)%P;}
int get1(int l,int r){return ((s2[l]-s2[r+1]*fac[r-l+1])%P+P)%P;}
signed main()
{
	cin>>n;scanf("%s%s",st1+1,st2+1);
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*B%P;
	int ans=0;
	for(int i=1;i<=n;i++)s1[i]=(s1[i-1]*B+st1[i])%P;
	for(int i=n;i>=1;i--)s2[i]=(s2[i+1]*B+st1[i])%P;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=min(i-1,n-i),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-mid,i)==get1(i,i+mid))l=mid+1,res=mid;
			else r=mid-1;
		}
		d1[i]=res;
		ans=max(ans,res*2+1);
	}
	for(int i=1;i<n;i++)if(st1[i]==st1[i+1])
	{
		int l=0,r=min(i-1,n-i-1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-mid,i)==get1(i+1,i+mid+1))l=mid+1,res=mid;
			else r=mid-1;
		}
		e1[i]=res;
		ans=max(ans,res*2+2);
	}
	for(int i=1;i<=n;i++)s1[i]=(s1[i-1]*B+st2[i])%P;
	for(int i=n;i>=1;i--)s2[i]=(s2[i+1]*B+st2[i])%P;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=min(i-1,n-i),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-mid,i)==get1(i,i+mid))l=mid+1,res=mid;
			else r=mid-1;
		}
		d2[i]=res;
		ans=max(ans,res*2+1);
	}
	for(int i=1;i<n;i++)if(st2[i]==st2[i+1])
	{
		int l=0,r=min(i-1,n-i-1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-mid,i)==get1(i+1,i+mid+1))l=mid+1,res=mid;
			else r=mid-1;
		}
		e2[i]=res;
		ans=max(ans,res*2+2);
	}
	for(int i=1;i<=n;i++)s1[i]=(s1[i-1]*B+st1[i])%P;
	for(int i=n;i>=1;i--)s2[i]=(s2[i+1]*B+st2[i])%P;
	for(int i=1;i<=n;i++)
	{
		if(st1[i-d1[i]-1]!=st2[i+d1[i]])continue;
		int l=0,r=min(i-d1[i]-1,n-i-d1[i]+1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-d1[i]-mid,i-d1[i]-1)==get1(i+d1[i],i+d1[i]+mid-1))l=mid+1,res=mid;
			else r=mid-1;
		}
		ans=max(ans,d1[i]*2+1+res*2);
	}
	for(int i=1;i<=n;i++)
	{
		if(st1[i-d2[i]]!=st2[i+d2[i]+1])continue;
		int l=1,r=min(i-d2[i],n-i-d2[i]),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-d2[i]-mid+1,i-d2[i])==get1(i+d2[i]+1,i+d2[i]+mid))l=mid+1,res=mid;
			else r=mid-1;
		}
		ans=max(ans,d2[i]*2+1+res*2);
	}
	for(int i=1;i<n;i++)if(st1[i]==st1[i+1])
	{
		if(st1[i-e1[i]-1]!=st2[i+e1[i]+1])continue;
		int l=1,r=min(i-e1[i]-1,n-i-e1[i]),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-e1[i]-mid,i-e1[i]-1)==get1(i+e1[i]+1,i+e1[i]+mid))l=mid+1,res=mid;
			else r=mid-1;
		}
		ans=max(ans,e1[i]*2+2+res*2);
	}
	for(int i=1;i<n;i++)if(st2[i]==st2[i+1])
	{
		if(st1[i-e2[i]]!=st2[i+e2[i]+2])continue;
		int l=1,r=min(i-e2[i],n-i-e2[i]-1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-e2[i]-mid+1,i-e2[i])==get1(i+e2[i]+2,i+e2[i]+mid+1))l=mid+1,res=mid;
			else r=mid-1;
		}
		ans=max(ans,e2[i]*2+2+res*2);
	}
	for(int i=1;i<=n;i++)if(st1[i]==st2[i])
	{
		int l=1,r=min(i,n-i+1),res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(get(i-mid+1,i)==get1(i,i+mid-1))l=mid+1,res=mid;
			else r=mid-1;
		}
		ans=max(ans,res*2);
	}
	cout<<ans<<'\n';
	return 0;
}