我有一个值序列，我想知道它是否包含一定最小长度的重复子序列。例如:
1, 2, 3, 4, 5, 100, 99, 101, 3, 4, 5, 100, 44, 99, 101
包含两次子序列3, 4, 5, 100。它还包含子序列99, 101两次，但该子序列短两次，无需关心。
是否有一种有效的算法来检查这种子序列的存在性?我对序列的位置不是特别感兴趣(尽管这对验证很有帮助)，我主要只是对给定序列和最小子序列长度的真/假答案感兴趣。
到目前为止，我唯一的方法是蛮力搜索:对于序列中的每个项，找到该项出现的所有其他位置(已经是O(N^2))，然后从每个位置一次向前走一步，看看下一个项是否匹配，并继续前进，直到我找到不匹配或找到足够长度的匹配子序列。
我的另一个想法是建立一个所有序列的树，这样每个数字都是一个节点，它的子节点是在它之前的数字，无论这个节点碰巧已经在树中。
对于任意N的值都有O(k)解(k -整个序列的长度)
解决方案#1:
为输入序列构建后缀树(使用Ukkonen算法)。
遍历具有两个或多个子节点的节点，并检查其中是否至少有一个深度为>= N。
解决方案#2:
为输入序列构建后缀自动机。
遍历右上下文至少包含两个不同字符串的所有状态，并检查这些节点中是否至少有一个距离自动机的初始状态为>= N。
解决方案#3:
也可以使用后缀数组和最长公共前缀技术(为输入序列构建后缀数组，计算最长公共前缀数组，检查是否存在一对相邻的、长度至少为N的公共前缀)
在假定字母表长度为常数(字母表由输入序列的所有元素组成)的情况下，这些解具有O(k)的时间复杂度。
如果不是这种情况，仍然有可能获得O(k log k)最坏情况下的时间复杂度(通过将所有转换存储在树中或在map中的自动机中)或O(k)平均使用hashmap。
p。我在这里互换使用术语string和sequence
如果你只关心长度恰好为N的子序列(例如，如果只是想检查是否有重复项)，那么有一个二次解:对每个子序列使用KMP算法。
假设整个序列中有k个元素
对于每一个长度为N (O(k))的子序列:
- 建立失败函数(取O(N))
- 在序列的剩余部分中搜索它(占用O(k))
假设N <<k，整个算法确实是O(k^2)
由于您的列表是无序的，您将不得不访问每个项目至少一次。
我想的是，你首先通过你的列表，并创建一个字典，你存储的数字作为一个键与所有索引它出现在你的序列。如:
Key: Indices
1: 0
2: 1
3: 2, 8
....
其中数字1出现在索引0处，数字2出现在索引1处，数字3出现在索引2和8处，以此类推
创建后，您可以遍历字典键并开始将其与其他位置的序列进行比较。这将节省一些蛮力，因为您不必每次都通过初始序列重新访问每个数字。