一、基本概念
最长公共回文子串(Longest_Common_Palindrome_Substring):两个字符串中最长的公共子串并且是回文字符串的子串
二、算法
三、代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
const int N=2e5+5;
int ch[N][26],fa[N],len[N],ct,last;
int tag[N];
void ini();
int newnode();
void extend(int,int);
char s[N];
void work();
int main(){
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// int T;cin>>T;
// while(T--)
work();
}
void work(){
while(cin>>s+1){
ini();
for(int i=1;s[i];i++) extend(s[i]-'a',i),tag[last]=1;
cin>>s+1;
int ans=0;
last=0;
for(int i=1;s[i];i++){
extend(s[i]-'a',i);
if(tag[last]) ans=max(ans,len[last]);
}
cout<<ans<<'\n';
}
}
void extend(int c,int i){
int p=last;
while(s[i-len[p]-1]!=s[i]) p=fa[p];
if(!ch[p][c]){
int np=newnode(),q=fa[p];
while(s[i-len[q]-1]!=s[i]) q=fa[q];
fa[np]=ch[q][c],ch[p][c]=np;
len[np]=len[p]+2;
}
last=ch[p][c];
}
void ini(){
fa[0]=fa[1]=1;
len[1]=ct=-1;
last=0;
newnode(),newnode();
}
int newnode(){
memset(ch[++ct],0,sizeof(ch[0]));
tag[ct]=0;
return ct;
}
四、例题
https://ac.nowcoder.com/acm/contest/908/H
五、参考文章
https://blog.csdn.net/qq_36551189/article/details/79245675?tdsourcetag=s_pcqq_aiomsg