Tsinsen 最长双回文串

求最长双回文串,正反建回文树求最大。

题目链接:http://www.tsinsen.com/ViewGProblem.page?gpid=A1280

By:大奕哥

 #include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int M=; struct Palindromic_Tree{
    int nex[N][M];
    int fail[N];
    int cnt[N];
    int num[N];
    int len[N];
    int S[N];
    int last;
    int n;
    int p;
    
    int newnode(int l)
    {
        for(int i=;i<M;++i)nex[p][i]=;
        cnt[p]=;
        num[p]=;
        len[p]=l;
        return p++;
    }
    
    void init()
    {
        p=;
        newnode();
        newnode(-);
        last=;
        n=;
        S[n]=-;
        fail[]=;
    }
    
    int get_fail(int x){
        while(S[n-len[x]-]!=S[n])x=fail[x];
        return x;
    }
    
    int add(int c){
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);
        if(!nex[cur][c]){
            int now=newnode(len[cur]+);
            fail[now]=nex[get_fail(fail[cur])][c];
            nex[cur][c]=now;
            num[now]=num[fail[now]]+;
        }
        last=nex[cur][c];
        cnt[last]++;
        return len[last];
    }
    
    void count(){
        for(int i=p-;i>=;--i)cnt[fail[i]]+=cnt[i];
    }
}T;
char s[N];
int l[N];
void solve()
{
    T.init();
    int ll=strlen(s);
    for(int i=ll-;i>=;--i)
    {
        l[i]=T.add(s[i]);
    }
    T.init();int ans=;
    for(int i=;i<ll-;++i)
    {
        int tmp=T.add(s[i]);ans=max(ans,l[i+]+tmp);
    }
    printf("%d\n",ans);
}
int main()
{
    while(~scanf("%s",s))solve();
    return ;
}
上一篇:Eclipse 调试器:零距离接触实战技巧


下一篇:Python快速学习04:循环 & 函数