ref
主要是要理解“撑到“最长这个概念
（为啥我的代码这么长QAQ
#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
int n, pa[200005], pb[200005], ans;
ull bse1[200005], bse2[200005], hsa1[200005], hsa2[200005], hsb1[200005];
ull hsb2[200005];
const int mod1=19260817, mod2=1e9+7;
char sa[200005], sb[200005];
bool iseq(int a, int b, int c, int d){
if(a>b) return true;
ull sa1=0, sb1=0;
if(a)
sa1 = hsa1[a-1] * bse1[b-a+1] % mod1;
sa1 = (hsa1[b] - sa1 + mod1) % mod1;
if(d!=n-1)
sb1 = hsb1[d+1] * bse1[d-c+1] % mod1;
sb1 = (hsb1[c] - sb1 + mod1) % mod1;
if(sa1!=sb1) return false;
sa1 = sb1 = 0;
if(a)
sa1 = hsa2[a-1] * bse2[b-a+1] % mod2;
sa1 = (hsa2[b] - sa1 + mod2) % mod2;
if(d!=n-1)
sb1 = hsb2[d+1] * bse2[d-c+1] % mod2;
sb1 = (hsb2[c] - sb1 + mod2) % mod2;
if(sa1!=sb1) return false;
return true;
}
void manacher(char a[], int b[]){
int id=0, mx=0;
for(int i=1; i<n; i++){
if(i<mx) b[i] = min(b[2*id-i], mx-i);
else b[i] = 1;
while(a[i-b[i]]==a[i+b[i]]) b[i]++;
if(mx<i+b[i]) mx = i + b[i], id = i;
ans = max(ans, b[i]);
}
}
int main(){
cin>>n;
scanf("%s", sa);
scanf("%s", sb);
for(int i=n; i>=0; i--){
sa[2*i+1] = '#';
sa[2*i+2] = sa[i];
}
for(int i=n; i>=0; i--){
sb[2*i+1] = '#';
sb[2*i+2] = sb[i];
}
sa[0] = sb[0] = '$';
n = 2 * (n + 1);
bse1[0] = bse2[0] = 1;
for(int i=1; i<n; i++){
bse1[i] = bse1[i-1] * 131 % mod1;
bse2[i] = bse2[i-1] * 131 % mod2;
}
ull ff=0;
for(int i=0; i<n; i++){
ff = (ff * 131 % mod1 + sa[i]) % mod1;
hsa1[i] = ff;
}
ff = 0;
for(int i=0; i<n; i++){
ff = (ff * 131 % mod2 + sa[i]) % mod2;
hsa2[i] = ff;
}
ff = 0;
for(int i=n-1; i>=0; i--){
ff = (ff * 131 % mod1 + sb[i]) % mod1;
hsb1[i] = ff;
}
ff = 0;
for(int i=n-1; i>=0; i--){
ff = (ff * 131 % mod2 + sb[i]) % mod2;
hsb2[i] = ff;
}
manacher(sa, pa);
manacher(sb, pb);
ans--;
for(int i=1; i<n; i++){
int pos1=i-pa[i], pos2=i+pa[i]-2;
int l=0, r=min(pos1, n-pos2), mid, re;
while(l<=r){
mid = (l + r) >> 1;
if(iseq(pos1-mid+1, pos1, pos2, pos2+mid-1))
re = mid, l = mid + 1;
else r = mid - 1;
}
ans = max(ans, pa[i]+re-1);
}
for(int i=1; i<n; i++){
int pos1=i-pb[i]+2, pos2=i+pb[i];
int l=0, r=min(pos1, n-pos2), mid, re;
while(l<=r){
mid = (l + r) >> 1;
if(iseq(pos1-mid+1, pos1, pos2, pos2+mid-1))
re = mid, l = mid + 1;
else r = mid - 1;
}
ans = max(ans, pb[i]+re-1);
}
cout<<ans<<endl;
return 0;
}