[POI2006]OKR-Periods of Words

一个字符串是由有限个小写字母组成的序列，空序列也视为字符串。

若存在字符串 $B$ ，使得 $A=PB$ ，则称字符串 $P$ 是字符串 $A$ 的前缀。若 $P$ 是 $A$ 的前缀，且 $P$ 既不是空串，也不等于 $A$ ，则称 $P$ 是 $A$ 的真前缀。

若字符串 $Q$ 是 $A$ 的真前缀，并且 $A$ 是 $QQ$ 的前缀（不一定是真前缀），则称 $Q$ 是 $A$ 的一个周期。例如，字符串 abab 和 ababab 都是字符串 abababa 的周期。

字符串 $A$ 的最大周期是其最长的周期；如果 $A$ 不存在周期，则其最大周期为空串。例如，ababab 的最大周期是 abab，而 abc 的最大周期是空串。

给定一个长度为 $k$ 的字符串，请求出它的所有前缀的最大周期长度之和。

输入格式

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

第二行输入一个由 $k$ 个小写字母组成的字符串。

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

8
babababa

本题为 POI 2006 试题「OKR-Periods of Words」，题面与测试数据整理自 BZOJ 1511。

8
babababa