1459: 信号传输
内存限制：65535 MB
时间限制：1000 S
评测方式：文本比较
命题人：外部导入
提交：194
解决：66
题目描述
给定一个字符串s1，它是由某个字符串s2不断自我连接形成的。但是字符串s2是不确定的，现在只想知道它的最短长度是多少。
输入
第一行一个整数L，表示给出字符串的长度。
第二行给出字符串s1的一个子串，全由小写字母组成。
第二行给出字符串s1的一个子串，全由小写字母组成。
输出
仅一行，表示s2的最短长度。
样例输入 复制
8
cabcabca
样例输出 复制
3提示
样例输入输出解释
对于样例，我们可以利用 abc不断自我连接得到 abcabcabc ，读入的 cabcabca 是它的子串。
题目解析：
cabcabca
通过输出 next_[] 数组： -1 0 0 0 1 2 3 4 5
next_[i] = j 表示第 i 位置前最长公共前后缀的长度为 j 。
c 位置最长公共前后缀的长度为 0
a 位置最长公共前后缀的长度为 0
b 位置最长公共前后缀的长度为 0
c 位置最长公共前后缀的长度为 1
a 位置最长公共前后缀的长度为 2
b 位置最长公共前后缀的长度为 3
c 位置最长公共前后缀的长度为 4
a 位置最长公共前后缀的长度为 5
注意：字符串存储是从下标0开始的，所以 :
next_[1] 表示 a 前面的子串 {c} 最长公共前后缀的长度为 0 。
next_[2] 表示 b 前面的子串 {ca} 最长公共前后缀的长度为 0 。
next_[3] 表示 c 前面的子串 {cab} 最长公共前后缀的长度为 0 。
next_[4] 表示 a 前面的子串 {cabc} 最长公共前后缀的长度为 1 。
答案N - next[N] 可以这样理解：
从字符串的某一处开始到串末，和串首到某一处是完全相等的，其中最长的就是最长公共前后缀。