最长重复子数组（有重叠）

Question

给定一个任意数字的数组，我希望快速[时间和空间复杂度至少低于 O(n\xc2\xb2)，n = 数组长度]找到最长的子数组（数组中元素的连续段）重复（出现多次，或至少两次）。
\n除了所有值都是有效的 JavaScript 数字并且isFinite对于数组中的每个数字都成立之外，请不要假设数组中数字的任何界限。

\n

允许重叠，即允许子数组在其内部部分出现。例如，在数组中[1, 2, 1, 2, 1, 2]最长的重复子数组是[1, 2, 1, 2]。看这里

\n

[1, 2, 1, 2, 1, 2]\n^         ^        occurrence #1\n       ^        ^  occurrence #2\n

\n

两次出现重叠，但只要两次出现的起始索引或结束索引不同就可以。

\n

如果存在多个不同的重复子数组且它们都具有最长的长度，则答案可以是其中任何一个。然而，我怀疑任何能够找到一个答案的方法都可以同样轻松地找到所有答案。
\n此场景的一个示例是数组[1, 1, 2, 2]。子数组[1]和[2]都出现两次。其中任何一个都可以作为结果返回。

\n

最后，如果没有子数组出现多次，则答案是[]（空数组）。

\n

我最近遇到了“在数组中查找重复序列”的问题，但所有答案都慢得离谱。每个人都在使用 o(n\xc2\xb3) 个解决方案，而 o(n\xc2\xb2) 中只有一个答案。

\n

我正在寻找一种可以在几秒钟内处理长度高达几十万（100,000）的数组的方法。时间复杂度至少为次二次方。如果您也能提供解决方案的 JS 示例实现，那就太好了，因为我对某些数据结构的理解不是那么扎实

\n

抱歉问了这么长的问题，如果有任何不清楚的地方请告诉我。如果您有一个想法但不是完整的解决方案，请将其放在评论中，它仍然对我有帮助。

\n

如果有帮助的话我还举了一些例子：

\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

大批	结果
[1, 2, 5, 7, 1, 2, 4, 5]	[1, 2]
[9, 7, 0, 1, 6, 3, 6, 5, 2, 1, 6, 3, 8, 3, 6, 1, 6, 3]	[1, 6, 3]
[1, 2, 1, 2, 7, 0, -1, 7, 0, -1]	[7, 0, -1]
[1, 1, 1, 1]	[1, 1, 1]
[1, 1, 1]	[1, 1]
[1, 2, 3, 4, 2, 5]	[2]
[1, 2, 3, 4, 5]	[]
[1, 6, 2, 1, 6, 2, 1, 5]	[1, 6, 2, 1]

\n

\n

这里有一个生成数组大小为 100,000 的大型测试用例的函数供参考，答案是 [1, 2, 3, ..., 100] （从 1 到 100 的 100 个连续整数）

\n

function make_case() {\n    let array = [];\n    let number = 200;\n    for (let i = 0; i < 500; i++) {\n        array.push(number); array.push(number);\n        number++;\n    }\n    for (let i = 1; i < 101; i++) {\n        array.push(i);\n    }\n    for (let i = 0; i < 1700; i++) {\n        array.push(number); array.push(number);\n        number++;\n    }\n    for (let i = 1; i < 101; i++) {\n        array.push(i);\n    }\n    for (let i = 0; i < (100_000 - 500 * 2 - 100 - 1700 * 2 - 100) / 2; i++) {\n        array.push(number); array.push(number);\n        number++;\n    }\n    return array;\n}\n

\n

另一个重要的情况是new Array(100_000).fill(0)，答案是有 99,999 个零的数组。

\n

Answer 1

这可以通过在通用字母表上构建后缀数组来解决。最长重复子数组将是后缀数组中某些两个相邻元素之间的最长公共前缀（LCP）。

以下方法的时间复杂度为O(N log^2 (N))，空间复杂度为O(N)。运行时间主要由后缀数组的创建决定，因此可以通过使用更快的后缀数组构造算法（例如DC3）进一步优化。

function longestRepeatingSubarray(arr) {
    const n = arr.length, suff = [...arr.keys()], rank = [...arr], lcp = Array(n), tempRank = Array(n);
    tempRank[0] = 0;
    for (let jump = 1; jump < n; jump <<= 1) {
        const comp = (i, j) => rank[i] - rank[j] || (Math.max(i, j) + jump < n ? rank[i + jump] - rank[j + jump] : j - i);
        suff.sort(comp);
        for (let i = 1; i < n; i++) tempRank[i] = tempRank[i - 1] + !!comp(suff[i - 1], suff[i]);
        for (let i = 0; i < n; i++) rank[suff[i]] = tempRank[i];
    }
    for (let i = 0, k = 0; i < n; i++)
        if (rank[i] !== n - 1) {
            for (let j = suff[rank[i] + 1]; arr[i + k] === arr[j + k];) ++k;
            lcp[rank[i]] = k;
            if (k) --k;
        }
    let best = 0;
    for (let i = 1; i < n - 1; i++) if (lcp[i] > lcp[best]) best = i;
    return arr.slice(suff[best], suff[best] + lcp[best]);
}

console.log(...longestRepeatingSubarray([1, 2, 5, 7, 1, 2, 4, 5]));
console.log(...longestRepeatingSubarray([1, 2, 1, 2, 7, 0, -1, 7, 0, -1]));
function make_case(){let $=[],u=200;for(let e=0;e<500;e++)$.push(u),$.push(u),u++;for(let s=1;s<101;s++)$.push(s);for(let h=0;h<1700;h++)$.push(u),$.push(u),u++;for(let p=1;p<101;p++)$.push(p);for(let t=0;t<47700;t++)$.push(u),$.push(u),u++;return $}
const arr = make_case();
console.time(`${arr.length} elements`);
console.log(...longestRepeatingSubarray(arr));
console.timeEnd(`${arr.length} elements`);