#kMPybttg020203. 1467:Radio Transmission

1467:Radio Transmission

好的,这是整理好的题面,格式清晰。


题目描述

给你一个字符串,它是由某个字符串不断自我连接形成的(即原串是该字符串重复若干次后得到的串的一个子串)。
但是这个“某个字符串”是不确定的,现在只想知道它的最短长度是多少。

例如:
输入 cabcabca,可以由 "abc" 不断自我连接得到 abcabcabc...,输入串是该串的一个子串,所以最短可能的循环单元长度为 3。


输入格式

第一行一个整数 ( L ),表示字符串长度。
第二行一个长度为 ( L ) 的字符串,全由小写字母组成。

输出格式

输出一个整数,表示最短的可能不断自我连接形成该串的字符串的长度。


数据范围

( 1 \le L \le 10^6 )


输入样例

8
cabcabca

输出样例

3

样例解释

字符串长度 ( L=8 ),字符串为 cabcabca

可以找到一个最短的字符串 "abc",将它重复连接:
abcabcabc...,取其中连续 8 个字符可以得到 cabcabca(例如从第二个字符开始取)。

因此最短长度为 3。

注意:该原串可能不是由完整的若干个循环单元组成,可能是从中间截取的一段,但我们要找的是最短的循环单元长度,使得该串是该循环单元重复多次后得到的字符串的一个连续子串。


这样题目就完整了,包括题意、输入输出格式、数据范围、样例及解释。