Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

03/18
19:27
kmp

[bzoj 1355] Baltic2009 Radio Transmission

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 给你一个字符串,它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少.

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串,全由小写字母组成.

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出最短的长度

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

8
cabcabca

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

kmp,根据肉眼观察法可得知.....答案是n-fail[n]

c++:

pascal:

 

[bzoj 1355] Baltic2009 Radio Transmission