C++14(g++5.4) 解法, 执行用时: 484ms, 内存消耗: 2688K, 提交时间: 2020-08-22 21:19:27

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int p[maxn*2];//p数组需要开至少字符串两倍的空间
string s1,s2;
int p1[maxn];
int p2[maxn];

void Manacher(string &str,int p[])
{
	string s="$#";
	int len=str.size();
	for(int i=0;i<len;i++){
		s+=str[i];
		s+='#';
	}
	int mx=0,id=0,reslen=0,rescenter=0,start=0;
	len=s.length();
	for(int i=1;i<=len;i++){
		if(mx>i) p[i]=min(p[2*id-i],mx-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]])p[i]++;
		if(mx<i+p[i]){
			mx=i+p[i];
			id=i;
		}
		if(reslen<p[i]){
			reslen=p[i];        //最长回文串
			rescenter=i;        //最长回文的中点
			start=(i-p[i]+2)/2-1;   //最长回文的起点
		}
	}
	str=s;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n;
	cin>>n>>s1>>s2;
	int ans=1;
	Manacher(s1,p1);
	Manacher(s2,p2);
    for(int i=2;i<s1.size();i++){
        int x=max(p1[i],p2[i-2]);
        //cout<<x<<endl;
        while(s1[i-x]==s2[i+x-2]) x++;
        ans=max(ans,x);
    }
    cout<<ans-1<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 407ms, 内存消耗: 2900K, 提交时间: 2022-09-04 22:09:52

#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N=2e5+7;
string s1,s2;
int p1[N],p2[N],n;
void manacher(string &s,int p[]){
	string str="$#";
	for(int i=0;i<n;i++){
//		str=str+s[i]+'#';
		str+=s[i];
		str+='#';
	}
	int len=str.length();
	int mx=0,id=0;
	for(int i=1;i<len;i++){
		if(i<mx) p[i]=min(mx-i,p[2*id-i]);
		else p[i]=1;
		while(str[i+p[i]]==str[i-p[i]]) p[i]++;
		if(i+p[i]>mx){
			mx=i+p[i];
			id=i;
		}
	}
	s=str;
}


int main(){
	cin>>n;
	cin>>s1>>s2;
	manacher(s1,p1);
	manacher(s2,p2);
	int len=s1.length(),ans=1;
	for(int i=2;i<len;i++){
		int x=max(p1[i],p2[i-2]);
		while(s1[i-x]==s2[i-2+x]) x++;
		ans=max(ans,x);
	}
	printf("%d\n",ans-1);
}