<分区>
给定一个长度为 N(<=10^5) 的二进制字符串，我想求出该字符串的循环长度。 循环的长度将最多 1000 且至少 1。
例子:
110110110110 循环长度为3(图案重复为110)
000000 循环长度为1(图案重复为0)
1101101101 循环长度为3(图案重复为110)
我试图理解Floyd's cycle detection algorithm但我无法理解如何申请这个问题。
如何有效地解决这个问题？ (我想要一个在 O(NlogN) 或更好的时间内运行的算法)。
<分区>
给定一个长度为 N(<=10^5) 的二进制字符串，我想求出该字符串的循环长度。 循环的长度将最多 1000 且至少 1。
例子:
110110110110 循环长度为3(图案重复为110)
000000 循环长度为1(图案重复为0)
1101101101 循环长度为3(图案重复为110)
我试图理解Floyd's cycle detection algorithm但我无法理解如何申请这个问题。
如何有效地解决这个问题？ (我想要一个在 O(NlogN) 或更好的时间内运行的算法)。
最佳答案
下面是这个问题的线性解:
让我们计算给定字符串的前缀函数(类似于 Knuth-Morris-Pratt 的算法)。
答案总是n - p[n]，其中n是给定字符串的长度，p[i] 是字符串中 i-th 位置的前缀函数的值。证明:
周期不小于n - p[n]。之所以如此，是因为对于任何 k 周期，对于任何 i，s[i] = s[i + k]。因此，由于前缀函数的定义，n - p[n] 至少为 k。
周期不大于k = n - p[n]。这是因为 s[i] = s[i + k] 对于所有 i 由于前缀函数的定义，这意味着 k 是句点。
关于algorithm - 位串中的循环检测，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29047809/