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

Question

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

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

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

提前致谢

Answer 1

这个问题可以用 Knuth-Morris-Pratt 解决字符串匹配算法。在继续之前，请先熟悉故障链接的计算方式。

让我们将列表视为类似于值序列(如字符串)的东西。让列表/序列的大小为 n。

然后，您可以:

1. 找出列表中最长的适当前缀的长度，它也是一个后缀。令最长适当前缀后缀的长度为len。

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

更多信息:

• GeeksForGeeks article.
• Knuth-Morris-Pratt algorithm