题目链接：回文串
我终于也会回文自动机辣！
其实吗……我觉得回文自动机(听说这玩意儿叫\(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\n",solve()); return 0; }
BZOJ 3676 【APIO2014】 回文串