[APIO2014]回文串后缀自动机_Manancher

Code:
// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

#include <cstring>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 400000

#define N 28

#define LOG 25

#define ll long long

using namespace std;

int last=1,tot=1,n;

char str[maxn];

int ch[maxn][N],cnt[maxn],f[maxn],dis[maxn],rk[maxn],position[maxn];

int fa[maxn][LOG+1],st[maxn];

int C[maxn];

long long ans;

struct Suffix_Automaton{

    void ins(int c){

        int p=last,np=++tot; last=np; dis[np]=dis[p]+1,position[dis[np]]=np;

        while(p&&!ch[p][c])ch[p][c]=np,p=f[p];

        if(!p) f[np]=1;

        else{

            int q=ch[p][c],nq;

            if(dis[q]==dis[p]+1) f[np]=q;

            else{

                nq=++tot;

                dis[nq]=dis[p]+1;

                memcpy(ch[nq],ch[q],sizeof(ch[q]));

                f[nq]=f[q],f[q]=f[np]=nq;

                while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];

            }

        }

        cnt[last]=1;

    }

    void build(){

        for(int i=0;i<n;++i) ins(str[i]-'a');

        for(int i=1;i<=tot;++i) ++C[dis[i]];

        for(int i=1;i<=tot;++i) C[i]+=C[i-1];

        for(int i=1;i<=tot;++i) rk[C[dis[i]]--]=i;

        for(int i=tot;i>=1;--i) cnt[f[rk[i]]]+=cnt[rk[i]];

        for(int i=1;i<=tot;++i) fa[i][0]=f[i];

        for(int i=1;i<LOG;++i)

            for(int j=1;j<=tot;++j) fa[j][i]=fa[fa[j][i-1]][i-1];

    }

    void update(int l,int r)

    {

        int p=position[r+1];

        for(int j=st[r+1];j>=0;--j) if(dis[fa[p][j]]>=r-l+1) p = fa[p][j];

        ans=max(ans,(ll)cnt[p]*(r-l+1));

    }

}sam;

struct Manancher{

    int p[maxn];

    char s[maxn];

    int Init(){

        int len=strlen(str);

        s[0]='$',s[1]='#';

        int j=1;

        for(int i=0;i<len;++i)

            s[++j]=str[i],s[++j]='#';

        s[++j]='\0';

        return j;

    }

    void manancher(){

        int len=Init(),id=1,mx=1;

        for(int i=1;i<len;++i){

            if(mx>i) p[i]=min(p[2*id-i],mx-i);

            else p[i]=1;

            while(s[i-p[i]]==s[i+p[i]])

            {

                if(s[i-p[i]]>='a'&&s[i-p[i]]<='z') sam.update((i-p[i])/2-1,(i+p[i])/2-1);

                ++p[i];

            }

            if(mx<i+p[i]) id=i,mx=i+p[i];

        }

    }

}man;

int main(){

    //setIO("input");

    scanf("%s",str),n=strlen(str);

    for(int i=1;i<=n;++i) st[i]=st[i>>1]+1;

    sam.build(),man.manancher();

    printf("%lld",ans);

    return 0;

}
巴特西

[APIO2014]回文串后缀自动机_Manancher_倍增

最新文章

热门文章

巴特西

[APIO2014]回文串 后缀自动机_Manancher_倍增

最新文章

热门文章

[APIO2014]回文串后缀自动机_Manancher_倍增
