QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100
[+4]

# 801. 回文自动机

Statistics

题目描述

对于 S,记 cS(T) 表示 TS 中的出现次数。对所有回文串 T,求 max

输入格式

输入只有一行,包含一个字符串 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): 没有额外的限制。