1344 - 周期长度

对于一个仅含小写字母的字符串a,p为 a的前缀且p=a,那么我们称 p为 a 的 proper前缀。
规定字符串 Q表示a的周期,当且仅当 Q 是 a的proper前缀且 a 是 Q+Q 的前缀。若这样的字符串不存在,则 a 的周期为空串。
例如 Q:ab 是 a:abab 的一个周期,因为 Q 是 a的 proper 前缀,且Q+Q:abab是a的前缀。
求给定字符串所有前缀的最大周期长度之和。

输入

的第一行中有一个整数k(1≤k≤1000 000)表示字符串的长度。
下面的一行中,输入这个序列(英语字母表中的k个小写字母)。

输出

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

样例

输入

8
babababa

输出

24

提示

样例解释:
b 0
ba 0
bab 2(Q:ba,a:bab,Q+Q:baba;Q是a的前缀,a是Q+Q的前缀,故最大周期长度为2)
baba 2
babab 4
bababa 4
bababab 6
babababa 6

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题