Problem1047--「一本通 2.2 练习 2」OKR-Periods of Words

1047: 「一本通 2.2 练习 2」OKR-Periods of Words

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 2  Solved: 1
Submit Status Web Board

Creator:

Description

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

Input

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

Output

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

Sample Input

8
babababa

Sample Output

24

HINT

对于全部数据,1<k<1061\lt k\lt 10^61<k<106

Source/Category


Submit Status