luoguP3649 [APIO2014]回文串

题意

关于回文自动机的讲解见这里

由于回文串个数是\(O(n)\)的，直接回文自动机上统计并比较即可。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3*1e5+10;
int n;
ll ans;
char s[maxn];
struct PA
{
    int tot,last;
    int fail[maxn],len[maxn],cnt[maxn];
    int ch[maxn][30];
    inline void init()
    {
        fail[0]=1;
        len[0]=0;len[1]=-1;
        tot=1;last=0;
    }
    inline int getfail(int x,int n)
    {
        while(s[n-len[x]-1]!=s[n])x=fail[x];
        return x;
    }
    inline void build(char* s,int n)
    {
        s[0]='#';
        for(int i=1;i<=n;i++)
        {
            int p=getfail(last,i);
            if(!ch[p][s[i]-'a'])
            {
                int q=++tot;len[q]=len[p]+2;
                fail[q]=ch[getfail(fail[p],i)][s[i]-'a'];
                ch[p][s[i]-'a']=q;
            }
            cnt[last=ch[p][s[i]-'a']]++;
        }
    }
}pa;
int main()
{
    scanf("%s",s+1);n=strlen(s+1);
    pa.init();pa.build(s,n);
    for(int i=pa.tot;i;i--)pa.cnt[pa.fail[i]]+=pa.cnt[i];
    for(int i=1;i<=pa.tot;i++)ans=max(ans,1ll*pa.cnt[i]*pa.len[i]);
    printf("%lld",ans);
    return 0;
}

luoguP3649 [APIO2014]回文串

原文：https://www.cnblogs.com/nofind/p/12063828.html