本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1130. 【KMP】OKR-Periods of Words


Description

串是有限个小写字符的序列,特别的,一个空序列也可以是一个串。一个串P是串A的前缀,当且仅当存在串B,使得A=PB。如果P≠A并且P不是一个空串,那么我们说P是A的一个proper前缀。
定义Q是A的周期,当且仅当Q是A的一个proper前缀并且A是QQ的前缀(不一定要是proper前缀)。比如串abab和ababab都是串abababa的周期。串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候),比如说,ababab的最大周期是abab。串abc的最大周期是空串。
给出一个串,求出它所有前缀的最大周期长度之和。

Input

第一行一个整数k,表示串的长度。
接下来一行表示给出的串。

Output

输出一个整数表示它所有前缀的最大周期长度之和。

Samples

Input Copy
8
babababa
Output
24

Hint

对于全部数据,1<k<106

Source

信息学奥赛一本通·提高篇
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
My history solutions

You didn't submit any solution!
Submit your solution

Login Register