javascript - 在两个(或更多)数组中查找匹配的单元格序列的最有效方法是什么？

Question

示例 1

假设我有两个数组:

('n','v','a','n','i','n','n','v','a','n')
('a','n','n','n','v','a','n','v','n')

我想找到两者之间的所有匹配序列(可能超过两个单元格左右)，它们不是其他较长匹配项的子匹配项。这是我认为匹配的内容:

('n','n','v','a','n') = 数组 1 中的位置 5 和数组 2 中的位置 3

数组 1:('n','v','a','n','i','n','n','v','a','n')

数组 2:('a','n','n','n','v','a','n','v','n')

示例 2

('n','v','a','n','i','n','n','v','i','n')
('a','n','i','n','p','v','i','n','v','n')

这里，我们有不止一个序列，但它们更短如下:

('a','n','i','n') = 数组 1 中的位置 2 和数组 2 中的位置 0

('v','i','n') = 数组 1 中的位置 7 和数组 2 中的位置 5

数组 1:('n','v','a','n','i','n','a','v','我'，'n')

数组 2:('a','n','i','n','p','v','i','n' ,'v','n')

总结

两个示例中都有不止一个匹配项，但它们都存在于至少一个数组中的较大匹配项中。

那么可以实现这一点的最有效(低内存和高速的平衡，想想移动设备)代码是什么？ JavaScript 代码示例会很棒!

Answer 1

这是我在通用 LCS 上的 JavaScript 尝试，O(mn) 时空版本。由于我们逐行进行，因此可以通过仅重复使用两行来减少空间，完成后将第二行复制到第一行。

var example1 = [['n','v','a','n','i','n','n','v','a','n']
               ,['a','n','n','n','v','a','n','v','n']],

    example2 = [['n','v','a','n','i','n','n','v','i','n']
               ,['a','n','i','n','v','i','n','v','n']];

function f(as){
  var M = new Array(as[0].length),
      result = [];

  for (var i=0; i<as[0].length; i++){
    M[i] = new Array(as[1].length).fill(0);

    for (var j=0; j<as[1].length; j++){
      if (as[0][i] == as[1][j]){
        M[i][j] = M[i-1] && M[j-1] ? 1 + M[i-1][j-1] : 1;
      }
      if ((i == as[0].length - 1 || j == as[1].length - 1) && M[i][j] > 2){
        result.push([i - M[i][j] + 1,j - M[i][j] + 1,M[i][j]]);
      } else if (i > 1 && j > 1 && M[i][j] < M[i-1][j-1] && M[i-1][j-1] > 2){
        result.push([i - M[i-1][j-1],j - M[i-1][j-1],M[i-1][j-1]]);
      }
    }
  }

  return result;
}

console.log(JSON.stringify(f(example2))); // [[2,0,4],[6,3,4]]