题目描述

给我们一个字符串S,求该字符串的最长双回文串长度.
双回文串:如果一个串T可以表示为AB,且A和B都是回文串,则T是一个双回文串.

样例

输入

baacaabbacabb

输出

12

分析

枚举双回文串的分界点i,那么以i点为分界点的双回文串的长度就是以i结尾的最长回文串的长度加上以i+1开头的最长回文串的长度.
我们用a[i]表示以i结尾的最长回文串长度,b[i]表示以i开头的最长回文串长度,答案就是a[i]+b[i+1]的最大值.
所有我们可以建两颗PAM,分别插入S和S的反串,插入字符的过程更新一下a[i]和b[i]即可.

PAM

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
char s[N];
int slen,a[N],b[N],ans;//ai表示s以i结尾的最长回文子串长度,bi表示s(R)以i结尾的最长回文子串长度 
struct PAM{
    int tr[N][26],idx,last;
    int fail[N],len[N];
    void init(){
        len[0]=0,len[1]=-1;
        fail[0]=1,fail[1]=0;
        idx=2;
    } 
    int get_fail(int x,int i){
        while(s[i]!=s[i-len[x]-1])x=fail[x];
        return x;
    }
    void insert(char c,int i){
        int now=get_fail(last,i);
        if(!tr[now][c-'a']){
            int x=idx++;
            len[x]=len[now]+2;
            fail[x]=tr[get_fail(fail[now],i)][c-'a'];
            tr[now][c-'a']=x;
        }
        last=tr[now][c-'a'];
    }
}A,B;
int main(){
    cin>>s+1;
    int slen=strlen(s+1);
    A.init(),B.init();
    for(int i=1;i<=slen;i++){
        A.insert(s[i],i);
        a[i]=A.len[A.last];
    }
    reverse(s+1,s+1+slen);
    for(int i=1;i<=slen;i++){
        B.insert(s[i],i);
        b[slen-i+1]=B.len[B.last];
    }
    for(int i=1;i<slen;i++)ans=max(ans,a[i]+b[i+1]);
    cout<<ans;
    return 0;
}