P3435 [POI 2006] OKR-Periods of Words

题目描述

一个字符串是由有限个小写英文字母组成的序列。特别地，它可以是一个空序列，即由 0 个字母组成的序列。我们用 $A=BC$ 表示字符串 $A$ 是通过连接字符串 $B$ 和 $C$（按此顺序）得到的（即一个接一个地写在一起，没有任何空格等）。字符串 $P$ 是字符串 $A$ 的前缀，如果存在一个字符串 $B$，使得 $A=PB$。换句话说，$A$ 的前缀是 $A$ 的初始片段。此外，如果 $P\neq A$ 且 $P$ 不是一个空字符串，我们称 $P$ 是 $A$ 的一个真前缀。

字符串 $Q$ 是 $A$ 的周期，如果 $Q$ 是 $A$ 的一个真前缀且 $A$ 是字符串 $QQ$ 的前缀（不一定是真前缀）。例如，字符串 abab 和 ababab 都是字符串 abababa 的周期。字符串 $A$ 的最大周期是其周期中最长的一个，或者如果 $A$ 没有任何周期，则为一个空字符串。例如，ababab 的最大周期是 abab。abc 的最大周期是空字符串。

任务：编写一个程序：

从标准输入读取字符串的长度和字符串本身，计算其所有前缀的最大周期长度的总和，将结果写入标准输出。

输入格式

标准输入的第一行有一个整数 $k$ ($1 \le k \le 1\ 000\ 000$) - 字符串的长度。接下来的行中写有恰好 $k$ 个小写英文字母的序列 - 该字符串。

输出格式

标准输出的第一行，你的程序应该输出一个整数 - 输入中给定字符串的所有前缀的最大周期长度的总和。

输入输出样例 #1

输入 #1

8
babababa

输出 #1

24

说明/提示

（由 ChatGPT 4o 翻译）by luogu