algorithm - 在两个大数组中使用哪种算法来获得最长的字符串匹配？

Question

这个问题很容易解释:我们有两个大数组(32 位整数值)，我们必须找到给定数量的连续位置 (n) 以上的所有公共(public)序列。

例如，如果 n=3 并且要比较的数组是:

a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6]
b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0]

算法应该返回两个数组:

r0 = [5, 7, 3, 2]
r1 = [3, 2, 7, 4, 6]

(或更好，它与第一个数组的相对位置和匹配的连续字节数)。

我认为一个好的开始点是 Longest Common Substring Algorithm ，但也许有人知道更适合或完全适合我的问题的算法。

Answer 1

我认为使用后缀树查找 LCS 的算法非常适合。您以相同的方式构建后缀树，但在最后阶段，您不是在寻找具有两个字符串后代的最深节点。您正在寻找所有深度超过 n 且具有两个字符串的后代的节点。