python - 确定列表是否是周期性的python

Question

我很想找到一个函数来检查给定列表是否是周期性的并返回周期性元素。列表不会加载，而是动态生成和添加它们的元素，如果这个注释无论如何都会使算法更容易。

例如，如果函数的输入为[1,2,1,2,1,2,1,2]，则输出应为 (1,2)。

我正在寻找一些关于实现这一目标的更简单方法的提示和提示。

提前致谢，

标签： pythonalgorithm

Answer 1

这个问题可以通过字符串匹配的Knuth-Morris-Pratt算法来解决。在继续之前，请熟悉失败链接的计算方式。

让我们将列表视为一个值序列（如字符串）。让列表/序列的大小为n.

那么你也能：

1. 找到列表中最长的正确前缀的长度，这也是一个后缀。设最长正确前缀后缀的长度为len。

2. 如果n可被 整除n - len，则列表是周期性的，并且周期是大小的len。在这种情况下，您可以打印第一个len值。

更多信息：

• GeeksForGeeks 文章。
• Knuth-Morris-Pratt 算法