查找序列的周期

Question

我想解决这个问题：

对于给定的序列，a[0], a[1], a[2],..., a[n-1]，请找到序列的 "period"。
周期是对所有有效i满足a[i] = a[i+k]的最小整数k（k>=1），同时k是n的约数

我目前的解决方案是计算 n（这是 k）的所有约数并测试所有 k，但它需要 O(n * d(n))。我觉得很慢。
有什么高效的算法吗？

Answer 1

将 Z 算法 (here and here) 应用于给定序列。

然后找到第一个位置 i 使得

  i+z[i] = n

和

  n mod i = 0

如果i这样的值存在，则为最短周期