python - 数字列表 - 如何找到重复模式？

Question

我有一个数字列表。大量噪声中存在重复模式。

示例数据:

(1,2,50,10,100,25,12,30,20,1,20,10,100,25,12,50,30,2,10,100,25,12,50,30,30,40,20,40,1,2,50,20,50,30,30,10,100,25,12,10,100,25,12)

在此示例中，所需的模式是 10,100,25,12，但每次都会不同。

如何找到任何重复模式？

Answer 1

后缀树是查找字符串中重复子字符串的最有效解决方案。

这是 Python 实现的一个示例:https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/

如果您不想理会这样复杂的解决方案，您可以简单地遍历字符串，一次一个元素，如果每个元素不是“10”、“100”、“25”或“，则将其删除12"。最终，您将到达由“10”、“100”、“25”和“12”序列组成的第一个元素。

如果您的问题需要任何通用模式，您很可能希望使用后缀树，否则您会考虑大量的时间复杂性。