algorithm - 找到重复一次生成给定序列的子序列

Question

给定一个大小为 N 的序列，这是一个未知子序列的重复，你如何有效地找到子序列的大小 M？

例如:

input : 6651366513665136651366513 -> output : sequence of length 5 which is 66513
input : 11111111111111111111111111111 -> output : sequence of length 1 which is 1
input : 6651366513665136651366513665 -> output : sequence of length 5 which is 66513

• 序列的元素是正数，而不仅仅是数字。
• N 不是 M 的倍数，因为最后一个序列不必是完整的。例如 665 可以附加到第一个示例。

最简单的方法是:

assume the sub-sequence is of size x, test, if not correct increase x and try again or output x

我仍在设计另一种解决方案，它不像上面的那样具有 O(N^2) 时间复杂度。

注意:出于好奇，我正在解析一个需要从流分析中构建索引的媒体文件，我发现该索引遵循重复模式。与其解析 2h 文件，不如解析一分钟并猜测下一个 1h59m 的索引。

Answer 1

给定一个序列 S，要找到周期的长度，您只需找到 S+S 中第二次出现的 S >。例如:

搜索

6651366513665136651366513

在

66513665136651366513665136651366513665136651366513

表示序列第二次出现在索引 5 中。鉴于原始序列的长度为 25，您可以看到它重复了 5 次。

您可以使用任何您想要的子字符串搜索算法，例如KMP 保证 O(n) 复杂度。