题意
给你一个由小写拉丁字母组成的字符串 ss。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ss，求所有回文子串中的最大存在值。
由小写拉丁字母（a~z）组成的非空字符串 ss
解法
回文自动机入门题目
参考博客
感觉回文自动机跟后缀自动机差不多，虽然我不会后缀自动机，只会一点点后缀数组，但感觉回文自动机挺好用的在解决回文串问题上，之前网络赛有一道就是用回文自动机的解法，但我只会用马拉车，所以今天来学一波回文自动机
特点
- 每个节点代表一个回文子串
- 每个节点有三个属性：该回文子串的长度，该回文子串在原串中的出现次数，该回文串的fail指针指向的节点位置
- 时间复杂度： O(N∗log(字符集大小))
- 空间复杂度: O(N∗(字符集大小))
应用
- 求串S前缀0~i内本质不同回文串的个数
- 求串S内每一个本质不同回文串出现的次数
- 求串S内回文串的个数（其实就是1和2结合起来）
- 求以下标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;
}
京公网安备 11010502036488号