BZOJ [3676: [Apio2014]回文串]

题意：

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。

题解：

回文自动机水题，注意插入字符时求出的cnt数组并不是最后的出现次数，而应该还要加上以它为后缀的回文，也就是所有fail指向它的节点的贡献。

$AC$代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 3e5+50; char s[MAXN]; struct Trie{ int nxt[MAXN][26],fail[MAXN],len[MAXN],cnt[MAXN]; int sz,lst; inline void Init(){ fail[0] = fail[1] = 1; len[0] = 0,len[1] = -1; sz = lst = 1; s[0] = '#'; } inline void Insert(char ch,int en){ int root = lst; while(s[en]!=s[en-len[root]-1]) root = fail[root]; if(!nxt[root][ch-'a']){ len[++sz] = len[root] + 2; int tmp = fail[root]; while(s[en]!=s[en-len[tmp]-1]) tmp = fail[tmp]; fail[sz] = nxt[tmp][ch-'a']; nxt[root][ch-'a'] = sz; } lst = nxt[root][ch-'a']; cnt[lst]++; } inline void Solve(){ LL res = 0; for(int i=sz;i>=2;i--) cnt[fail[i]] += cnt[i]; for(int i=2;i<=sz;i++) res = max(res,1LL*len[i]*cnt[i]); printf("%lld\n",res); } }PAM; int main(){ scanf("%s",s+1); PAM.Init(); for(int i=1;s[i];i++) PAM.Insert(s[i],i); PAM.Solve(); return 0; }