algorithm - 检查序列中长度 >= N 的重复子序列

Question

我有一个值序列，我想知道它是否包含某个最小长度的重复子序列。例如:

1, 2, 3, 4, 5, 100, 99, 101, 3, 4, 5, 100, 44, 99, 101

包含子序列 3, 4, 5, 100 两次。它还包含子序列 99, 101 两次，但该子序列很短，需要关心。

是否有一种有效的算法来检查这种子序列的存在？我对序列的位置不是特别感兴趣(尽管这有助于验证)，我主要只对给定序列和最小子序列长度的真/假答案感兴趣。

到目前为止我唯一的方法是暴力搜索它:对于序列中的每个项目，找到该项目出现的所有其他位置(已经在 O(N^2))，然后向前走一步每个位置的时间并查看下一个项目是否匹配，并继续前进，直到我发现不匹配或找到足够长度的匹配子序列。

我曾想过但未能发展成实际方法的另一个想法是构建所有序列的树，以便每个数字都是一个节点，并且是它前面数字的子节点，无论节点恰好已经在树中。

Answer 1

对于 O(k) 的任意值，有 k 个解决方案( N - 整个序列的长度)。

解决方案 #1:
为输入序列构建后缀树(使用 Ukkonen 算法)。
遍历具有两个或更多子节点的节点，并检查其中是否至少有一个具有深度 >= N 。

解决方案 #2:
为输入序列构建一个后缀自动机。
迭代所有状态，其中右上下文至少包含两个不同的字符串，并检查这些节点中是否至少有一个距离为 >= N从自动机的初始状态开始。

解决方案#3:
也可以使用后缀数组和最长公共(public)前缀技术(为输入序列构建后缀数组，计算最长公共(public)前缀数组，检查是否有一对相邻的公共(public)前缀长度至少为 N 的前缀)。

假设字母表大小不变(字母表由输入序列的所有元素组成)，这些解决方案的时间复杂度为 O(k)。
如果不是这种情况，仍然有可能获得 O(k log k) 的最坏情况时间复杂度(通过将所有转换存储在树中或在 map 中的自动机中)或平均使用 O(k) 获得 hashmap。

P.S 我在这里互换使用术语 string 和 sequence。