[POI 2006] 字符串的 OKR-周期

题目描述

字符串是由小写英文字母组成的有限序列。特别地，字符串可以是空序列，即长度为 0 的序列。我们用 $A=BC$ 表示字符串 $A$ 是由字符串 $B$ 和字符串 $C$ 按顺序拼接（直接相连，无空格等分隔符）得到的。

若存在字符串 $B$，使得 $A=PB$，则称字符串 $P$ 是字符串 $A$ 的前缀。换句话说，字符串 $A$ 的前缀就是它的开头子串。 此外，如果 $P \neq A$ 且 $P$ 不是空字符串，我们称 $P$ 是 $A$ 的真前缀。

若字符串 $Q$ 是 $A$ 的真前缀，且 $A$ 是字符串 $QQ$ 的前缀（不必是真前缀），则称 $Q$ 是 $A$ 的周期。 例如：字符串 $\texttt{abab}$ 和 $\texttt{ababab}$ 都是字符串 $\texttt{abababa}$ 的周期。

字符串 $A$ 的最大周期是它所有周期中最长的那个；如果 $A$ 没有任何周期，则最大周期为空字符串。 例如：$\texttt{ababab}$ 的最大周期是 $\texttt{abab}$；$\texttt{abc}$ 的最大周期是空字符串。

任务

编写程序完成以下要求：

1. 从标准输入读取字符串长度和字符串本身；
2. 计算该字符串所有前缀的最大周期的长度之和；
3. 将结果输出到标准输出。

输入格式

第一行输入一个整数 $k$（$1\le k\le 1\ 000\ 000$），表示字符串的长度。 第二行输入一个长度恰好为 $k$ 的小写英文字符串。

输出格式

仅输出一行一个整数，表示输入字符串所有前缀的最大周期的长度之和。

输入样例

8
babababa

输出样例

24

提示

（暂无提示）

标签：P3435|字符串|2006|POI（波兰）|KMP 算法

来源

P3435|[POI 2006] OKR-Periods of Words