Luogu

分析

先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。

这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。

考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一段是 $B$ 中继续向右扩展出的串。

容易发现后两段相反，二分答案并利用哈希 check() 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef unsigned long long ull;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const ull BASE=19491001;

int n; char a[N],b[N];

ull pw[N],ha[N],hb[N];
inline ull gethash(int op,int l,int r) {
    if (op==1) return ha[r]-ha[l-1]*pw[r-l+1];
    if (op==2) return hb[l]-hb[r+1]*pw[r-l+1];
}

int f[N],g[N]; char c[N];
inline void change(char* s) {
    for (re int i=1;i<=n;++i) c[i]=s[i];
    for (re int i=1;i<=n;++i) s[i<<1]=c[i],s[i<<1|1]='#';
    s[0]='?',s[1]='#',s[(n+1)<<1]='\0';
}
inline void manacher(char* s,int* f) {
    for (re int i=1,mid,mr=0;i<=n;++i) {
        f[i]=i<mr?min(f[(mid<<1)-i],mr-i):1;
        while (s[i-f[i]]==s[i+f[i]]) ++f[i];
        if (i+f[i]>mr) mid=i,mr=i+f[i];
    }
}

inline int calc(int x,int y) {
    if (x<1||y>n||a[x<<1]!=b[y<<1]) return 0;
    int L=1,R=min(x,n-y+1);
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (gethash(1,x-mid+1,x)==gethash(2,y,y+mid-1)) L=mid;
        else R=mid-1;
    }
    return L;
}

int main() {
    n=read(); scanf("%s%s",a+1,b+1);
    pw[0]=1; for (re int i=1;i<=n;++i) pw[i]=pw[i-1]*BASE;
    for (re int i=1;i<=n;++i) ha[i]=ha[i-1]*BASE+a[i];
    for (re int i=n;i>=1;--i) hb[i]=hb[i+1]*BASE+b[i];
    change(a),change(b),n=n<<1|1,manacher(a,f),manacher(b,g);
    int ans=0;
    for (re int i=1;i<=n;++i) ans=max(ans,f[i]-1);
    for (re int i=1;i<=n;++i) ans=max(ans,g[i]-1);
    for (re int i=1;i<=n;++i) { int L,R;
        L=(i-f[i])/2+1,R=(i+f[i])/2-1;
        ans=max(ans,f[i]-1+(calc(L-1,R)<<1));
        L=(i-g[i])/2+1,R=(i+g[i])/2-1;
        ans=max(ans,g[i]-1+(calc(L,R+1)<<1));
    }
    printf("%d\n",ans);
    return 0;
}