C++(g++ 7.5.0) 解法, 执行用时: 28ms, 内存消耗: 12464K, 提交时间: 2023-03-30 18:48:27

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int N=200005;
int pam[N][26],fail[N],len[N],pam_cnt,last,ni,vis[N],vis_cnt[N];
string s[3];

void init()
{
	last=0;
	len[1]=-1;
	s[1][0]='?',s[2][0]='?';
	fail[0]=fail[1]=1;
}

int get_fail(int x, int id)
{
	while(s[id][ni-len[x]-1]!=s[id][ni])
		x=fail[x];
	return x;
}

void add(int c, int id)
{
	int old=get_fail(last, id);
	if(!pam[old][c])
	{
		int now=++pam_cnt;
		memset(pam[now],0,sizeof(pam[now]));
		vis[now]=vis_cnt[now]=0;
		fail[now]=pam[get_fail(fail[old], id)][c];
		pam[old][c]=now;
		len[now]=len[old]+2;
	}
	last=pam[old][c];
	if(vis[last]!=id)
		vis[last]=id,vis_cnt[last]++;
}

int main()
{
	while(cin>>s[1]>>s[2])
	{
		pam_cnt=1;
		memset(pam[1],0,sizeof(pam[1]));
		memset(pam[0],0,sizeof(pam[0]));
		s[1]=' '+s[1];
		s[2]=' '+s[2];
		init();
		for(ni=1; ni<s[1].size(); ni++)
			add(s[1][ni]-'a', 1);
		init();
		for(ni=1; ni<s[2].size(); ni++)
			add(s[2][ni]-'a', 2);
		int maxl=0;
		for(int i=1; i<=pam_cnt; i++)
			if(vis_cnt[i]==2)
				maxl=max(maxl, len[i]);
		cout << maxl << '\n';
	}
	return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 11932K, 提交时间: 2021-08-18 11:35:12

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <cstring>
#include <sstream>

using namespace std;
const int N=1e5+5;
char s[N];
int tag[N],tr[N][26],len[N],pre[N],last,ct;
int newnode(){
    memset(tr[++ct],0,sizeof(tr[0]));
    tag[ct]=0;
    return ct;
}
void add(int c,int i){
    int p=last;
    while(s[i-len[p]-1]!=s[i])p=pre[p];
    if(!tr[p][c]){
        int np=newnode(),q=pre[p];
        while(s[i-len[q]-1]!=s[i])q=pre[q];
        pre[np]=tr[q][c],tr[p][c]=np;
        len[np]=len[p]+2;
    }
    last=tr[p][c];
}
void init(){
    pre[0]=pre[1]=1;
    len[1]=ct=-1;
    last=0;
    newnode(),newnode();
}
int main()
{
    
    while(~scanf("%s",s+1)){init();
    for(int i=1;s[i];i++)add(s[i]-'a',i),tag[last]=1;
    scanf("%s",s+1);
    int ans=0;last=0;
    for(int i=1;s[i];i++){
        add(s[i]-'a',i);
        if(tag[last])ans=max(ans,len[last]);
    }
    printf("%d\n",ans);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 228K, 提交时间: 2019-06-03 21:47:49

#include<stdio.h>
int main() {
    printf("7\n9\n11\n100000\n35\n");
}