4944：[POI 2006] OKR-Periods of Words

# [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