P3649 [APIO2014]回文串 【回文自动机/回文树】

题意

给你一个由小写拉丁字母组成的字符串 ss。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ss，求所有回文子串中的最大存在值。
由小写拉丁字母（a~z）组成的非空字符串 ss

解法

回文自动机入门题目
参考博客

感觉回文自动机跟后缀自动机差不多，虽然我不会后缀自动机，只会一点点后缀数组，但感觉回文自动机挺好用的在解决回文串问题上，之前网络赛有一道就是用回文自动机的解法，但我只会用马拉车，所以今天来学一波回文自动机
特点

• 每个节点代表一个回文子串
• 每个节点有三个属性：该回文子串的长度，该回文子串在原串中的出现次数，该回文串的fail指针指向的节点位置
• 时间复杂度： $O(N\ast log(字符集大小\left)\right)$O(N∗log(字符集大小))
• 空间复杂度: $O(N\ast (字符集大小\left)\right)$O(N∗(字符集大小))

应用

1. 求串S前缀0~i内本质不同回文串的个数
2. 求串S内每一个本质不同回文串出现的次数
3. 求串S内回文串的个数（其实就是1和2结合起来）
4. 求以下标i结尾的回文串的个数

下面的代码套了模板：

/* author: anthony1314 时间复杂度：O(N*log(26)) 空间复杂度: O(N*(26)) 26 字符集大小 */
#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
typedef long long ll;
struct Palindrome_Automaton {
   /* len[i]： 节点i的回文串的长度 next[i][c]： 节点i的回文串在两边添加字符c以后变成的回文串的编号(和字典树的next指针类似) fail[i]： 类似于AC自动机的fail指针，指向失配后需要跳转到的节点（即为i的最长回文后缀且不为i） cnt[i]： 节点i表示的回文串在S中出现的次数（建树时求出的不是完全的，count()加上子节点以后才是正确的） num[i]： 以节点i回文串的末尾字符结尾的但不包含本条路径上的回文串的数目。(也就是fail指针路径的深度) last： 指向以字符串中上一个位置结尾的回文串 cur： 指向由next构成的树中当前回文串的父亲节点（即当前回文串是cur左右两边各拓展一个字符得来） S[i]： 第i次添加的字符 p： 添加的节点个数 n： 添加的字符个数 */

   int len[MAXN], next[MAXN][26], fail[MAXN], cnt[MAXN], last, cur, S[MAXN], p, n;
   int newnode(int l) {
   	for (int i = 0; i < 26; i++) {
   		next[p][i] = 0;
   	}
   	cnt[p] = 0;
   	len[p] = l;
   	return p++;
   }
   void init() {
   	p = n = last = 0;
   	newnode(0);
   	newnode(-1);
   	S[0] = -1;
   	fail[0] = 1;
   }
   int get_fail(int x) {
   	while (S[n - len[x] - 1] != S[n]) {
   		x = fail[x];
   	}
   	return x;
   }
   void add(int c,int pos) { //插字符
   	c -= 'a';
   	S[++n] = c;
   	int cur = get_fail(last);
   	if (!next[cur][c]) {
   		int now = newnode(len[cur] + 2);
   		fail[now] = next[get_fail(fail[cur])][c];
   		next[cur][c] = now;
   	}
   	last = next[cur][c];
   	cnt[last]++;
   }
   void count() { //统计本质相同的回文串的出现次数
   	//逆序累加，保证每个点都会比它的父亲节点先算完，于是父亲节点能加到所有子孙
   	for (int i = p-1; i >= 0; i--) {
   		cnt[fail[i]] += cnt[i];
   	}
   }
} run;
char s[MAXN];

int main() {
   scanf("%s", s);
   run.init();
   int len = strlen(s);
   for (int i = 0; i < len; i++) {
   	run.add(s[i], i);
   }
   run.count();
   ll ans = 0;
   for (int i = 2; i < run.p; i++) {//从2开始
   	ans = max(ans, (ll)run.len[i] * run.cnt[i]);
   }
   printf("%lld\n", ans);
   return 0;
}