C++14(g++5.4) 解法, 执行用时: 671ms, 内存消耗: 2536K, 提交时间: 2020-03-29 13:17:49

#include <bits/stdc++.h>
using namespace std;
const int AX = 2e5 + 666 ;
char a[AX] , b[AX] ;
int pa[AX] , pb[AX] ;
int n ;
void manacher( char *s , int *p ){
	for( int i = n ; i >= 0 ; i-- ){
		s[2*i+2] = s[i] ;
		s[2*i+1] = '#' ;
	}
	s[0] = '$';
	int id = 0 , mx = 0 ; 
	for( int i = 2 ; i <= 2 * n ; i++ ){
		if( p[id] + id > i ) p[i] = min( p[id] + id - i , p[2*id-i] ) ;
		else p[i] = 1 ;
		while( s[i+p[i]] == s[i-p[i]] ) p[i] ++ ;
		if( i + p[i] > mx ){
			mx = p[i] + i ; 
			id = i ;
		}
	}
}
int main() {
	cin >> n ;
	cin >> a >> b ;
	manacher( a , pa ); 
	manacher( b , pb );
	int res = 0 ; 
	for( int i = 2 ; i <= 2 * n ; i++ ){
		int tmp = max( pa[i] , pb[i-2] );
		while( a[i-tmp] == b[i+tmp-2] ) tmp ++ ;
		res = max( res , tmp );
	}
	cout << res - 1 << endl;
	return 0 ;
}

C++(clang++11) 解法, 执行用时: 395ms, 内存消耗: 2708K, 提交时间: 2020-11-03 21:29:13

#include<bits/stdc++.h>
using namespace std;
int p1[200005];
int p2[200005];
string a,b;
string manacher(string a,int *p)
{
	string t="$#";
	int len=a.length();
	for(int i=0;i<len;i++)
	{
		t+=a[i];
		t+="#";
	}
	int mx=0,id=0;
	int tlen=t.size();
	for(int i=1;i<tlen;i++)
	{
		p[i]=mx>i?min(p[2*id-i],mx-i):1;
		while(t[i+p[i]]==t[i-p[i]])++p[i];
		if(mx<i+p[i])
		{
			mx=i+p[i];
			id=i;
		}
	}
	return t;
}
int main()
{
	int n;
	cin>>n;
	cin>>a>>b;
	a=manacher(a,p1);
	b=manacher(b,p2);
	int ans=0;
	n=n*2+1;
	for(int i=2;i<n;i++)
	{
		int temp=max(p1[i],p2[i-2]);
		while(a[i-temp]==b[i-2+temp]) temp++;
		ans=max(temp,ans);
	 } 
	 cout<<ans-1<<endl;
}