题目链接：回文串
我终于也会回文自动机辣！
其实吗……我觉得回文自动机(听说这玩意儿叫(PAM))还是比较(simple)的……至少比(SAM)友善多了……
所谓回文自动机，每个节点就代表一个回文串。回文自动机的每个节点有两个东西，一个是(next)，一个是(fail)。(next_{u,x})指向节点(u)所代表的回文串在两端各添加一个字符(x)得到一个新的回文串。(fail_u)则指向(u)这个节点的最长后缀回文串(不包括本身)。当然还有一个(len)数组记录每个节点代表的回文串的长度。
构造自动机之前首先需要构造两个节点(0)，(1)。其中(len_0=0)，(len_1=-1)，并且(fail_0=1)。(0)号点代表的是空串，(1)号点代表的是不存在的串。
然后我们考虑如何加入一个字符。我们加入第(n)个字符(c)，从以上个字符结尾的回文串(x)开始，一路跳(fail)直到我们找到了一个回文串为止。即如果(s)数组存了我们需要构建自动机的字符串，那么(x)节点满足(s_n=s_{n-len_x-1})。不难发现，这样跳最多到(1)号点就终止了。然后，如果(next_{x,c})存在，那么说明这个回文串已经出现过了，给它的次数加(1)即可。否则，我们就需要新建一个节点(p)，那么显然(len_p=len_x+2)。到这里，(len_1=-1)的好处就显现出来了，让我们少了一个特判。然后，我们还需考虑(fail_p)。我们从(fail_x)开始找起，每次跳(fail)，直到找到了一个回文串满足(s_n=s_{n-len_x-1})为止。然后，(fail_p)就等于(next_{x,c})了。
说了这么多，写起来还是很好写的。这道题就是板子题。下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 300010
using namespace std;
typedef long long llg;
char a[maxn];
int l[maxn],s[maxn][26],f[maxn],tt,v[maxn],la;
llg ans;
void add(int c,int n){
int p=la;
while(a[n-l[p]-1]!=a[n]) p=f[p];
if(!s[p][c]){
int np=++tt,k=f[p]; l[np]=l[p]+2;
while(a[n-l[k]-1]!=a[n]) k=f[k];
f[np]=s[k][c]; s[p][c]=np;
}
v[la=s[p][c]]++;
}
llg solve(){
llg ans=0;
for(int i=tt;i>1;i--) v[f[i]]+=v[i],ans=max(ans,1ll*l[i]*v[i]);
return ans;
}
int main(){
File("a");
l[++tt]=-1; f[0]=1;
scanf("%s",a+1); int n=strlen(a+1);
for(int i=1;i<=n;i++) add(a[i]-'a',i);
printf("%lld
",solve());
return 0;
}