Cyclic Nacklace （kmp中next数组的运用）
Cyclic Nacklace （kmp中next数组的运用）。
【题意】
题意是给出一个字符串，要求变成一个周期串，最少需要几个字符？
【思路】
也不知道怎地，想到了next数组，数组里记录的数字可以看成是一个周期。
举例说明：
字符串abcabcabc
next数组：0 0 0 1 2 3 4 5 6
而字符串abcabc
next数组：0 0 0 1 2 3
因为有大于0的数字的说明前面有重复的，并且，若是连续出现这样的会数字，说明一直连续，那不就是周期串了吗。。只需要字符总个数减去最后一位的next值，就可以得到最小循环周期，当然，可能会想这样的例子：
abcabcabcaca
0 0 0 1 2 3 4 5 6 7 0 1
那么这个字符串的最小周期是几呢？
答案是11。
【代码】
#include#include
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻