BZOJ 1355 [Baltic2009]Radio Transmission

发布于 2017-04-08  172 次阅读


题意:给定一个字符串,求它的最小循环节。(给定串可以是循环串的一部分)

HINT 中的样例是错误的,正确的循环节应该是 cab。

对于 KMP 算法的 next(fail)数组,具有这样一个性质:

n-next[n] 即为原串的最小循环节

上述性质证明:

(未完待续)


一个非常弱的准退役OIER