最长公共连续子序列 - 算法

Question

我的问题很简单：是否有 O(n) 算法来查找两个序列 A 和 B 之间最长的连续子序列？我搜索了它，但所有结果都是关于 LCS 问题的，这不是我想要的。

注意：如果您愿意提供任何示例代码，我们非常欢迎您这样做，但如果可以，请使用 C 或 C++。

编辑：这是一个例子：

A: { a, b, a, b, b, b, a }
B: { a, d, b, b, b, c, n }
longest common contiguous subsequence: { b, b, b }

Answer 1

是的，您可以在线性时间内完成此操作。一种方法是为模式和文本构建后缀树并计算它们的交集。不过，我想不出一种在不涉及后缀树或后缀数组的情况下做到这一点的方法。