BZOJ 1355 [Baltic2009]Radio Transmission


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

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

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

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

上述性质证明:

(未完待续)

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1355 [Baltic2009]Radio Transmission


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: