3794. [POI 2012]Prefixuffix

【题目描述】

如果能把字符串的一个后缀移动到开头得到另一个字符串，则这两个字符串称为「循环等价」。

给定由 $n$ 个小写字母组成的字符串 $t$，求它的一个长度相同的前缀和后缀，满足：

  $(1)$前缀和后缀循环等价；

  $(2)$前缀和后缀的长度不超过 $\frac n2$（即在 $t$ 内不相交）；

  $(3)$满足上述条件的情况下，使前缀和后缀的长度最大。

【输入格式】

第一行一个正整数 $n$ ，表示字符串 $t$ 的长度。

接下来一行为字符串 $t$，由 $n$ 个小写字母组成。

【输出格式】

输出一个整数，表示前缀和后缀的长度。

【样例1输入】

15
ababbabababbaab

【样例1输出】

6

【样例1说明】

ababba 和 abbaab「循环等价」

【样例2输入】

5
aaaaa

【样例2输出】

2

【样例3/4/5输出】

点击下载样例3/4/5

【样例6/7/8输入输出】

点击下载样例6/7/8

【数据规模与约定】

对于 $30\%$ 的数据，保证 $n \le 500$；

对于 $50\%$ 的数据，保证 $n \le 5000$；

对于 $100\%$ 的数据，保证 $n \le 1\ 000\ 000$。