hdu 1358 Period (kmp,求字符串的周期)

hdu 1358 题目链接

题意:给一个字符串,求这个字符串的每个前缀(包括本身)的能否由k个子串组成(K>1)

思路:和poj 2406 比较类似。。

结论:字符编号从0开始,如果又i%(i-next[i])==0,则i前面的
串为一个轮回串,其中轮回子串出现i/(i-next[i])次。

证明类似之前最小覆盖中的,不断的等价交换,两两相等…(这个证明在字符串这里总是遇到2333)

然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333.

之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律,猜结论。。。

 

 

 

&nbs

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz