javascript - 查找两个数组的最长公共(public)后缀的最佳方法

Question

给定两个数组，我需要找到最长的公共(public)后缀。

更准确地说，我需要找到每个数组中的索引，之后会出现该后缀。

例如:

// Input
arr1 = [1,2,3,4,5,6];
arr2 = [11,12,13,5,6];

// Output
ind1 = 4;
ind2 = 3;

这是我的代码:

let ind1 = arr1.length - 1;
let ind2 = arr2.length - 1;
while (ind1 >= 0 && ind2 >= 0 && arr1[ind1] == arr2[ind2]) {
    ind1--;
    ind2--;
}
ind1++;
ind2++;

是否有我可以在这里应用的单语句技巧(或一般来说“更干净”的方法)？

Answer 1

这绝对不是单语句技巧或更简洁的方法，但它本质上比您现有的代码做的要多得多。

根据讨论:

What if arrays are like: [1,2,3,4,5,6,7,8,9], [1,2,6,5,4,7,8,9]? – Rajesh

@Rajesh: Try the code. It should give you ind1 = 0 and ind2 = 0. – goodvibration

@goodvibration I need to find the longest common suffix, so longest suffix is 7,8,9 and not 1,2 – Rajesh

Oh, sorry, I thought they were identical in your example. Yes, the suffix here is 7,8,9, so the output should be ind1 = 6 and ind2 = 5. – goodvibration

您正在寻找返回最大序列起始索引的逻辑。为此，您必须捕获所有序列并在返回索引之前检查它们的长度。

您可以尝试以下逻辑:

• 创建一个临时对象来保存位置。
• 现在遍历数组。
  • 如果 Array1 的起始位置未定义，则查找匹配元素的索引。
  • 将此索引保存在临时对象中并继续。
  • 如果定义了 startPosition，则在两个数组中查找下一个值是否相等。
  • 如果相等，继续。
  • 如果没有，创建一个组并从该索引重新开始该过程。

function getLongestSuffixIndex(a1, a2) {
  var temp = {}
  var groups = [];
  var lastA2Index = 0;
  var a2Index = -1;
  var part;

  function addGroup() {
    if (temp.startA1Index !== undefined) {
      groups.push({
        a1Index: temp.startA1Index,
        a2Index: temp.startA2Index,
        count: temp.endA1Index - temp.startA1Index + 1
      });
      temp = {};
    }
  }

  function checkForIndex(i) {
    a2Index = part.indexOf(a1[i]);
    if (a2Index >= 0) {
      temp.startA1Index = i;
      temp.startA2Index = a2Index + lastA2Index;
      lastA2Index += a2Index;
    }
  }

  for (var i = 0, len = a1.length; i < len; i++) {
    part = a2.slice(lastA2Index);
    if (temp.startA1Index === undefined) {
      checkForIndex(i);
    } else {
      var index = (temp.startA2Index || 0) + (temp.count|| 0) + 1
      if (a1[i] === a2[index]) {
        temp.endA1Index = i;
        temp.count = i - temp.startA1Index;
      } else {
        addGroup();
        checkForIndex(i);
      }
    }
  }
  addGroup();

  return groups.length ? groups.reduce(function(p, c) {
    return ((p.count || 0) > (c.count || 0)) ? p : c
  }) : undefined;
}

var arr1 = [1, 2, 3, 4, 5, 6];
var arr2 = [11, 12, 13, 5, 6];

console.log(getLongestSuffixIndex(arr1, arr2))
console.log(getLongestSuffixIndex([1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 6, 5, 4, 7, 8, 9]))