题目描述
给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s中出现的次数乘以这个子串的长度。对于给你的这个字符串 s，求所有回文子串中的最大存在值。
输入格式
一行，一个由小写拉丁字母（a~z）组成的非空字符串 s。
输出格式
输出一个整数，表示所有回文子串中的最大存在值。
样例
输入样例 1
abacaba
输出样例 1
7
输入样例 2
www
输出样例 2
4
首先建出s的回文树，然后对于每一个回文子串，记录cnt为它出现的次数。
对于它fail树上的儿子，肯定都是它的子串（后缀），所以他出现了cnt次，它的后缀也会出现cnt次。
我们从更新的节点从后往前遍历，假设现在遍历到i，就使cnt[fail[i]]+=cnt[i]。然后更新ans=max(ans, cnt[i]*len[i])。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 400000; char s[N]; int lens; long long ans; namespace Plalindromic_Tree{ struct node{ int go[26]; int fail, len; }pt[N]; int lst = 0, tot = 0; int cnt[N]; void build() { s[0] = -1; pt[++tot].len = -1; pt[0].fail = pt[1].fail = 1; } void add(int c, int n) { int p = lst; while (s[n - pt[p].len - 1] != s[n]) p = pt[p].fail; if (!pt[p].go[c]) { int v = ++tot, k = pt[p].fail; pt[v].len = pt[p].len + 2; while (s[n - pt[k].len - 1] != s[n]) k = pt[k].fail; pt[v].fail = pt[k].go[c]; pt[p].go[c] = v; } lst = pt[p].go[c]; cnt[pt[p].go[c]]++; } }using namespace Plalindromic_Tree; int main() { scanf("%s", s + 1); lens = strlen(s + 1); build(); for (int i = 1; i <= lens; i++) { add(s[i] - ‘a‘, i); } for (int i = tot; i; i--) { cnt[pt[i].fail] += cnt[i]; ans = max(ans, 1ll * cnt[i] * pt[i].len); } cout << ans; return 0; }