QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

# 801. 回文自动机

Statistics

题目描述

对于 $S$,记 $c_S(T)$ 表示 $T$ 在 $S$ 中的出现次数。对所有回文串 $T$,求 $\max_T(c_S(T) \cdot |T|^2)$。

输入格式

输入只有一行,包含一个字符串 $S$。

输出格式

输出一行一个整数,表示答案。

样例数据

样例 1 输入

hyddakioizjoi

样例 1 输出

9

样例 1 解释

取 $T=\mathsf{ioi}$。

样例 2 输入

hyakioivilavpnshadowsocksapioioihyakioiagain

样例 2 输出

36

样例 2 解释

取 $T=\mathsf{ioi}$。

子任务

对于所有数据,$|S| \leq 10^6$。

  • Subtask 1(35 Points): $|S| \leq 3.5 \times 10^4$。
  • Subtask 2(65 Points): 没有额外的限制。