3887. [POI 2006]单词的周期

【题目描述】

一个**字符串**是由小写英文字母组成的有限序列。特别地，它也可以是空序列（即长度为 $0$ 的序列）。

如果字符串 $A$ 是通过字符串 $B$ 和 $C$ 按顺序连接（中间没有任何间隔符号）得到的，我们表示为 $A=BC$。

如果存在一个字符串 $B$ 使得 $A=PB$，那么字符串 $P$ 是字符串 $A$ 的**前缀**。此外，如果 $P \neq A$ 且 $P$ 不是空字符串，我们称 $P$ 是 $A$ 的**真前缀**。

如果 $Q$ 是 $A$ 的真前缀，并且 $A$ 是字符串 $QQ$ 的前缀（不一定是真前缀），那么字符串 $Q$ 是 $A$ 的**周期**。例如，字符串 `abab` 和 `ababab` 都是 `abababa` 的周期。

字符串 $A$ 的**最大周期**是其最长的周期，如果 $A$ 没有周期，则为空字符串。例如，`ababab` 的最大周期是 `abab`；`abc` 的最大周期是空字符串。

编写一个程序，计算该字符串所有前缀的最大周期长度之和。

【输入格式】

第一行包含一个整数 $k$，表示字符串的长度。

接下来的一行包含一个由 $k$ 个小写英文字母组成的字符串。

【输出格式】

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

【样例输入】

8
babababa

【样例输出】

24

【数据范围】

对于所有数据，$1\le k\le10^6$。