【模板】Manacher(Manacher)
【模板】Manacher(Manacher)
题目描述
给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 ,求 中最长回文串的长度 。
字符串长度为 。
输入格式
一行小写英文字符 $\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z$ 组成的字符串 。
输出格式
一个整数表示答案。
样例输入 #1
aaa
样例输出 #1
3
数据范围
。
知识点与难度
本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。
测试点分布
| Subtask | 分值 | 测试点编号 | 说明 |
|---|---|---|---|
| 0 | 10 | 1 | 样例 |
| 1 | 20 | 2~7 | 小规模 n≤5000 / 特殊: n=1单字符 / 特殊: 26字母严格递增最长回文为1 / 偶数长中心回文 |
| 2 | 8~13 | 中等规模 n≤200000 / Hack: 全相同字符与多级倍增分形回文串卡朴素中心扩展O(n^2) | |
| 3 | 25 | 14~21 | 大规模 n≤2000000 奇偶混合超长回文串线性Manacher测试 |
| 4 | 22~25 | 满规模 n=11000000 极限1.1×10^7长度线性时间与内存压力测试 |
出处：原题链接