检测一系列字符何时重复，其时间复杂度优于 O(n!)

Question

我需要找到一系列字符（实际上是一个很长的数字）何时开始重复。我认为模式是最简单的。有人可以帮助我吗？

Answer 1

如果是数字，则从末尾开始。

找到最后一个 n 和倒数第二个 n 数字相同且重复最大位数的序列。 O(n)

重复序列停止的地方（从末尾开始）就是重复开始的地方。

例如，假设您有 1.2340111101111

您可以看到 1 重复，但仅限 4 位数字。 01111 重复 10 位数字，表示在 1.234 之后开始重复

Answer 2

根据此序列的来源，这可能有用。

Answer 3

我不懂Java。我不确定你的确切问题，但似乎你正在尝试找到序列的最大轨道。下面的伪代码应该会有所帮助：

Given sequence M of length N
Initialize list of indices K
foreach index i from N-1 to N/2
    seqLength := N-i
    isOrbit? := true
    foreach index s from 0 to seqLength-1
        if M[N-1-s] != M[N-1-seqLength-s] then
            isOrbit? := false
    if isOrbit? then
       append(K, i)

当然，最长的轨道是添加到 K 的最后一个条目。该算法约为 O(n^2/4) 左右。本质上，它是一种改进的子序列搜索算法。