我的问题是：我的数字序列很大。我知道，在某个点之后，它变成周期性的- 也就是说，序列的开头有k个数字，然后在序列的其余部分又有m个重复的数字。例如，为了使这一点更加清楚，序列可能如下所示：[1、2、5、3、4、2、1、1、3、2、1、1、3、2、1、1、3 ，…]，其中k为5，m为4，则重复块为[2，1，1，3]。从该示例可以清楚地看出，我可以在较大的块中包含重复的位，因此仅查找重复的第一个实例无济于事。
但是，我不知道k或m是什么-我的目标是采用序列[a_1，a_2，…，a_n]作为输入并输出序列[a_1，…，a_k，[a_（k +1），…，a_（k + m）]]-通过将大部分序列列为重复块来基本上截断更长的序列。
是否有解决此问题的有效方法？此外，可能更难但更理想的计算- 在生成有问题的序列时是否可以执行此操作，因此我必须生成最少的数量？我在该站点上看过其他类似的问题，但它们似乎都处理序列而没有开始的非重复位，并且通常不必担心内部重复。
如果有帮助/有用，我也可以弄清楚为什么我要看这个以及我将用它做什么。
谢谢！
编辑：首先，我应该提到，我不知道输入序列是否恰好在重复块的结尾处结束。
我正在尝试解决的现实问题是为二次无理数（实际上是负CFE）的连续分数展开（CFE）写一个漂亮的闭式表达式。为这些CFE生成部分商*达到任何精确度都是非常简单的- 但是，在某个点上，用于二次无理数的CFE的尾部成为重复块。我需要在此重复块中使用部分商。
我目前的想法是：也许我可以改编一些建议使用的算法，从正确的角度开始使用这些序列之一。另外，也许有一些证据可以证明为什么二次非理性是周期性的，这将帮助我了解为什么它们会重复出现，这将帮助我提出一些容易检查的标准。
*如果我将连续分数扩展写为[a_0，a_1，…]，则将a_i称为部分商。
一些感兴趣的人可以在这里找到一些背景信息：http : //en.wikipedia.org/wiki/Periodic_continued_fraction
您可以使用 滚动散列 来实现线性时间复杂度和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的筛子，方法是将下一次希望重复的时间保留在优先队列中。
最后，我们仔细检查结果以确保没有哈希冲突（即使有，也不会出现黑名单并重复）。
在这里，我假设您的目标是使非重复长度最小化，并且不给出可以进一步考虑的重复元素；您可以修改此算法以查找所有其他压缩（如果存在）。
