题目地址：洛谷：【P3649】[APIO2014]回文串 – 洛谷、BZOJ：Problem 3676. — [Apio2014]回文串

题目描述

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

输入输出格式

输入格式：
输入只有一行，为一个只包含小写字母(a-z)的非空字符串s。

输出格式：
输出一个整数，为所有回文子串的最大出现值。

输入输出样例

输入样例#1：

abacaba

输出样例#1：

7

输入样例#2：

www

输出样例#2：

4

说明

【样例解释1】
用 ∣s∣ 表示字符串 s 的长度。
一个字符串 s1s2…s∣s∣ 的子串是一个非空字符串 sisi+1…sj ，其中 1≤i≤j≤∣s∣ 。每个字符串都是自己的子串。
一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。
这个样例中，有 7 个回文子串 a，b，c，aba，aca，bacab，abacaba。他们的存在值分别为 4,2,1,6,3,5,7 。
所以回文子串中最大的存在值为 7 。
第一个子任务共 8 分，满足 1≤∣s∣≤100 。
第二个子任务共 15 分，满足 1≤∣s∣≤1000 。
第三个子任务共 24 分，满足 1≤∣s∣≤10000 。
第四个子任务共 26 分，满足 1≤∣s∣≤100000 。
第五个子任务共 27 分，满足 1≤∣s∣≤300000 。

题解

回文自动机直接做就行了，注意小回文串的siz值要加上大回文串的siz值，因此可以倒序（拓扑序）遍历PAM更新答案。
复杂度$O(n)$。

代码

参考资料：「BZOJ3676」[Apio2014] 回文串 – 后缀自动机 – manacher – hzwer.com

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

const int MAXN = 300005;

int n;
char s[MAXN];
LL ans;

struct PalindromeAutomaton {
    int ch[MAXN][26], fail[MAXN], len[MAXN], siz[MAXN], tot, lst;
    PalindromeAutomaton() {
        tot = 1; fail[0] = fail[1] = 1; len[1] = -1;
    }
    inline void extend(int c, int n) {
        int p = lst;
        while(s[n - len[p] - 1] != s[n]) p = fail[p];
        if(!ch[p][c]) {
            int now = ++tot, k = fail[p];
            len[now] = len[p] + 2;
            while(s[n - len[k] - 1] != s[n]) k = fail[k];
            fail[now] = ch[k][c]; ch[p][c] = now;
        }
        lst = ch[p][c]; siz[lst]++;
    }
    inline void solve() {
        for(int i = tot; i; i--) {
            siz[fail[i]] += siz[i];
            ans = std::max(ans, 1ll * siz[i] * len[i]);
        }
    }
} pam;

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i++) {
        pam.extend(s[i] - 'a', i);
    }
    pam.solve();
    printf("%lld", ans);
    return 0;
}