题目描述

给我们一个字符串长度n,一个字符串S,求最长双倍回文子串长度.
双倍回文子串:一个形如A A(R) A A(R)的字符串称为双倍回文子串,例如:abbaabba.
|S|<=5e5

样例

输入

16
ggabaabaabaaball

输出

12

分析

首先双倍回文子串一定是个回文串,我们把字符串S插入到PAM中,节点至多只有n个,那我们就可以枚举每一个回文子串,只要判断该回文子串所在节点的fail链上存不存在长度是他一半的border即可.如果暴力跳fail链,时间复杂度会达到n^2,我们可以用倍增的思想,将时间复杂度将为nlogn.

PAM+倍增

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int vec[20];
int tr[N][26],idx,last,tot;
int fail[N],len[N];
int n;
char s[N];
int f[N][20],depth[N];
int ans=-1;
int q[N];
vector<int>h[N];
int node(int x){
    len[idx++]=x;
    return idx-1;
}
void init(){
    node(0);
    node(-1);
    fail[1]=0,fail[0]=1;
    vec[0]=1;
    for(int i=1;i<20;i++)vec[i]=2*vec[i-1];
}
int get_fail(int x){
    while(s[tot-len[x]-1]!=s[tot])x=fail[x];
    return x;
}
void insert(char c){
    tot++;
    int now=get_fail(last);
    if(!tr[now][c-'a']){
        int x=node(len[now]+2);
        int t=get_fail(fail[now]);
        fail[x]=tr[t][c-'a'];
        h[tr[t][c-'a']].push_back(x);
        tr[now][c-'a']=x;
    }
    last=tr[now][c-'a'];
}
void bfs(){
    int tt=0,hh=0;
    memset(depth,0x3f,sizeof depth);    
    q[tt++]=0,q[tt++]=1;
    depth[0]=depth[1]=0;
    for(int i=0;i<20;i++)f[1][i]=1;
    while(tt!=hh){
        int t=q[hh++];
        for(int i=0;i<h[t].size();i++){
            int j=h[t][i];
            if(depth[j]>depth[t]+1){
                q[tt++]=j;
                depth[j]=depth[t]+1;
                f[j][0]=t;
                for(int k=1;k<20;k++){
                    f[j][k]=f[f[j][k-1]][k-1];
                }
            }
        }

    }
}
bool get_(int u,int x){
    for(int i=19;i>=0;i--){
        if(len[f[u][i]]>=x)u=f[u][i];
    }
    if(len[u]==x)return true;
    else return false;
}
int main(){
    cin>>n;
    cin>>s+1;
    init();
    for(int i=1;i<=n;i++)insert(s[i]);
    bfs();
    for(int i=idx-1;i>1;i--){
        if(len[i]%4==0&&get_(i,len[i]/2))ans=max(ans,len[i]);
    }
    cout<<ans;
    return 0;
}