【APIO2014】—回文串（回文自动机）

传送门

回文自动机简单题

因为不想学后缀自动机做法，于是去大概把回文自动机学了

感觉比后缀自动机简单多了啊

很显然就是$fail$树上$max(siz[u]*len[u])$

然后…就完了啊

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
} 
const int N=300005;
char a[N];
struct pam{
    int ch[27],fail,len,cnt;
}p[N];
int n,tot,last;
ll ans;
int main(){
    scanf("%s",a+1);
    n=strlen(a+1),a[0]='#';
    p[0].fail=1,p[1].len=-1,++tot;
    for(int i=1;i<=n;i++){
        while(a[i-p[last].len-1]!=a[i])last=p[last].fail;
        if(!p[last].ch[a[i]-'a']){
            p[++tot].len=p[last].len+2;
            int j=p[last].fail;
            while(a[i-p[j].len-1]!=a[i])j=p[j].fail;
            p[tot].fail=p[j].ch[a[i]-'a'];
            p[last].ch[a[i]-'a']=tot;
        }
        last=p[last].ch[a[i]-'a'];
        p[last].cnt++;
    }
    for(int i=tot;i>=2;i--){
        p[p[i].fail].cnt+=p[i].cnt;
        if((ll)p[i].cnt*p[i].len>ans)ans=(ll)p[i].cnt*p[i].len;
    }
    cout<<ans;
}