Bzoj3676:[Apio2014]回文串:回文自动机

题目链接：3676:[Apio2014]回文串

回文自动机复习一发！

话说我的会回文自动机入门题居然不是这个？！

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=600010;
char s[maxn];
int cnt[maxn];

struct pam{
	int next[maxn][26],l[maxn],ro,re;
	int sz,last,fail[maxn];
	void init(){
		sz=0; s[0]='@';
		sz++; ro=sz; l[ro]=-1; memset(next[sz],0,sizeof(next[sz]));
		sz++; re=sz; l[re]=0;  memset(next[sz],0,sizeof(next[sz]));
		fail[ro]=ro; fail[re]=ro; last=ro;
	}
	bool gofail(int x,int c,int id){
		return s[id-l[x]-1]-'a'==c;
	}
	void add(int c,int id){
		while (!gofail(last,c,id)) last=fail[last];
		if (next[last][c]) last=next[last][c];
		else{
			int x=last; ++sz; next[x][c]=sz; l[sz]=l[x]+2;
			memset(next[sz],0,sizeof(next[sz]));
			if (x==ro){
				fail[sz]=re;
			}else{
				x=fail[x];
				while (!gofail(x,c,id)) x=fail[x];
				fail[sz]=next[x][c];
			}last=sz;
		}cnt[last]++;
	}
}pt;

int main(){
	pt.init();
	scanf("%s",s+1);
	int len=strlen(s+1);
	for (int i=1;i<=len;++i) pt.add(s[i]-'a',i);
	LL ans=1;
	for (int i=pt.sz;i;i--){
		cnt[pt.fail[i]]+=cnt[i];
		ans=max(ans,1LL*cnt[i]*pt.l[i]);
	}
	printf("%lld",ans);
}