最长公共回文子串(Longest_Common_Palindrome_Substring)

一、基本概念

最长公共回文子串(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