arrays - 在数字序列的末尾查找重复序列

Question

我的问题是:我有一大串数字。我知道，在某个点之后，它会变成周期性的——也就是说，序列的开头有 k 个数字，然后还有 m 个数字在序列的其余部分重复。为了更清楚地说明这一点，序列可能如下所示:[1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...]，其中 k 为 5，m 为 4，则重复 block 为 [2, 1, 1, 3]。从这个例子中可以清楚地看出，我可以在较大的 block 内有重复位，因此只查找第一个重复实例并没有帮助。

但是，我不知道 k 或 m 是什么 - 我的目标是将序列 [a_1, a_2, ... , a_n] 作为输入并输出序列 [a_1, ... , a_k, [ a_(k+1), ... , a_(k+m)]] - 基本上是通过将大部分序列列为重复 block 来截断较长序列。

有没有一种有效的方法来解决这个问题？此外，在计算上可能更难但更理想 - 是否可以在我生成有问题的序列时执行此操作，以便我必须生成最小数量？我在这个网站上看过其他类似的问题，但它们似乎都处理没有开始非重复位的序列，而且通常不必担心内部重复。

如果它有帮助/有用，我还可以了解我为什么要看这个以及我将用它做什么。

谢谢!

编辑:首先，我应该提到我不知道输入序列是否恰好在重复 block 的末尾结束。

我试图解决的现实问题是为二次无理数(实际上是负 CFE)的连分数展开式 (CFE) 编写一个漂亮的封闭式表达式。为这些 CFE 生成任何精度的部分商*非常简单 - 然而，在某些时候，二次无理数的 CFE 的尾部变成重复 block 。我需要处理这个重复 block 中的部分商数。

我目前的想法是:也许我可以调整一些建议的算法，从右边开始工作，以处理其中一个序列。或者，也许在证明二次无理数为什么是周期性的证据中可以帮助我理解为什么它们开始重复，这将帮助我提出一些简单的标准来检查。

*如果我将连分数展开写为 [a_0, a_1, ...]，我将 a_i 称为部分商。

感兴趣的人可以在这里找到一些背景信息:http://en.wikipedia.org/wiki/Periodic_continued_fraction

Answer 1

您可以使用 rolling hash实现线性时间复杂度和 O(1) 空间复杂度(我认为是这种情况，因为我不相信你可以有一个无限重复的序列，其中两个频率不是彼此的倍数)。

算法:您只需保留两个滚动散列，它们会像这样展开:

                       _______  _______  _______
                      /       \/       \/       \
...2038975623895769874883301010883301010883301010
                      .        .        .      ||
                      .        .        .    [][]
                      .        .        .  [ ][ ]
                      .        .        .[  ][  ]
                      .        .       [.  ][   ]
                      .        .     [  . ][    ]
                      .        .   [    .][     ]
                      .        . [      ][      ]
                      .        [       ][       ]

在整个序列中继续这样做。第一遍将只检测重复 2*n 次的某些 n 值。然而，这不是我们的目标:我们在第一遍中的目标是检测所有可能的周期，而这正是这样做的。当我们沿着执行此过程的顺序前进时，我们还会跟踪所有我们稍后需要检查的相对黄金时期:

periods = Set(int)
periodsToFurthestReach = Map(int -> int)

for hash1,hash2 in expandedPairOfRollingHashes(sequence):
    L = hash.length
    if hash1==hash2:
        if L is not a multiple of any period:
            periods.add(L)
            periodsToFurthestReach[L] = 2*L
        else L is a multiple of some periods:
            for all periods P for which L is a multiple:
                periodsToFurthestReach[P] = 2*L

在这个过程之后，我们得到了所有时期的列表以及它们已经达到了多远。我们的答案可能是覆盖范围最远的那个，但我们会检查所有其他时间段是否重复(速度很快，因为我们知道要检查的时间段)。如果这在计算上很困难，我们可以通过在遍历列表时修剪掉周期(停止重复)来优化，非常像 Eratosthenes 的筛子，通过保留我们下一次期望周期重复的时间的优先级队列。

最后，我们仔细检查结果以确保没有哈希冲突(即使有也不太可能，列入黑名单并重复)。

这里我假设你的目标是最小化非重复长度，而不是给出可以进一步分解的重复元素；您可以修改此算法以查找所有其他压缩(如果存在)。