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

Question

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

例如,如果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]

algoritmh应该返回两个数组:

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

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

我相信一个好的开始是最长公共子串算法,但也许任何人都知道一个算法更符合我的问题.

Answer 1

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