给定两个序列，找到一个序列的结尾和另一个序列的开头之间的最大重叠
Given two sequences, find the maximal overlap between ending of one and beginning of the other
我需要找到一个有效的（伪）代码来解决以下问题：
给定两个（不一定不同）整数序列 (a[1], a[2], ..., a[n]) 和 (b[1], b[2], ..., b[n])，找到最大值 d 使得 a[n-d+1] == b[1], a[n-d+2] == b[2], . ..，和 a[n] == b[d].
这不是作业，我实际上是在尝试沿尽可能多的维度收缩两个张量时想到的。我怀疑存在一个有效的算法（也许 O(n)？），但我想不出不是 O(n^2) 的东西。 O(n^2) 方法将是 d 上的明显循环，然后是项目上的内部循环以检查所需条件，直到达到最大值 d。但我怀疑可能会有比这更好的东西。
对于 O(n) time/space 复杂度，诀窍是评估每个子序列的哈希值。考虑数组 b:
[b1 b2 b3 ... bn]
使用Horner's method，您可以评估每个子序列的所有可能哈希值。选择一个基值 B（大于两个数组中的任何值）：
from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n
请注意，您可以使用前一个序列的结果在 O(1) 时间内评估每个序列，因此所有作业的成本为 O(n)。
现在你有一个数组 Hb = [h(b1), h(b2), ... , h(bn)]，其中 Hb[i] 是从 b1 到 bi.
的散列
对数组 a 做同样的事情，但有一个小技巧：
from an to an = (an * B^1)
from an-1 to an = (an-1 * B^1) + (an * B^2)
from an-2 to an = (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an = (a1 * B^1) + (a2 * B^2) + (a3 * B^3) + ... + (an * B^n)
您必须注意，当您从一个序列步进到另一个序列时，您将整个前一个序列乘以 B，然后加上乘以 B 的新值。例如：
from an to an = (an * B^1)
for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2)
hence:
from an-1 to an = (an-1 * B^1) + (an * B^2)
现在你有一个数组 Ha = [h(an), h(an-1), ... , h(a1)]，其中 Ha[i] 是从 ai 到 an.
的散列
现在，您可以比较 Ha[d] == Hb[d] 从 n 到 1 的所有 d 值，如果它们匹配，您就有答案了。
ATTENTION: this is a hash method, the values can be large and you may have to use a fast exponentiation method and modular arithmetics, which may (hardly) give you collisions, making this method not totally safe. A good practice is to pick a base B as a really big prime number (at least bigger than the biggest value in your arrays). You should also be careful as the limits of the numbers may overflow at each step, so you'll have to use (modulo K) in each operation (where K can be a prime bigger than B).
这意味着两个不同的序列可能具有相同的散列值，但是两个相等的序列总是具有相同的散列值。
您可以利用 z algorithm 线性时间 (O(n)) 算法：
Given a string S of length n, the Z Algorithm produces an array Z
where Z[i] is the length of the longest substring starting from S[i]
which is also a prefix of S
您需要将您的数组 (b+a) 和 运行 算法连接到生成的构造数组上，直到第一个 i 这样 Z[i]+i == m+n.
例如，对于 a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0]，串联将是 [2, 3, 6, 2, 1, 0, 1, 2, 3, 6, 2, 3]，这将产生 Z[ 10] = 2 满足 Z[i] + i = 12 = m + n.
这确实可以在线性时间内完成，O(n)，并且 O(n) 额外 space .我假设输入数组是字符串，但这不是必需的。
一个朴素的方法——在匹配 k 个相等的字符后——找到一个不匹配的字符，然后返回 k-1 单位 a，重置 b 中的索引，然后从那里开始匹配过程。这显然代表了 O(n²) 最坏的情况。
为了避免这种回溯过程，我们可以观察到，如果我们在扫描最后的 k-1 个字符时没有遇到 b[0] 字符，则回溯是没有用的。如果我们 did 找到那个字符，那么回溯到那个位置只会有用，如果在那个 k 大小的子字符串中我们有一个周期性的重复。
例如，如果我们查看 a 中某处的子字符串 "abcabc"，而 b 是 "abcabd" , 并且我们发现 b 的最后一个字符不匹配，我们必须考虑到一个成功的匹配可能从子字符串中的第二个 "a" 开始，我们应该移动我们的b 中的当前索引在继续比较之前相应地返回。
然后我们的想法是根据字符串 b 进行一些预处理，以在 b 中记录反向引用，这有助于检查何时有一个不匹配。因此，例如，如果 b 是 "acaacaacd"，我们可以识别这些基于 0 的反向引用（放在每个字符下方）：
index: 0 1 2 3 4 5 6 7 8
b: a c a a c a a c d
ref: 0 0 0 1 0 0 1 0 5
例如，如果 a 等于 "acaacaaca"，则第一个不匹配发生在最后一个字符上。上面的信息然后告诉算法返回 b 到索引 5，因为 "acaac" 是常见的。然后只需更改 b 中的当前索引，我们就可以在 a 的当前索引处继续匹配。在此示例中，最后一个字符的匹配成功。
这样我们就可以优化搜索，确保a中的索引总能向前推进。
下面是 JavaScript 中该想法的实现，仅使用该语言的最基本语法：
function overlapCount(a, b) {
// Deal with cases where the strings differ in length
let startA = 0;
if (a.length > b.length) startA = a.length - b.length;
let endB = b.length;
if (a.length < b.length) endB = a.length;
// Create a back-reference for each index
// that should be followed in case of a mismatch.
// We only need B to make these references:
let map = Array(endB);
let k = 0; // Index that lags behind j
map[0] = 0;
for (let j = 1; j < endB; j++) {
if (b[j] == b[k]) {
map[j] = map[k]; // skip over the same character (optional optimisation)
} else {
map[j] = k;
}
while (k > 0 && b[j] != b[k]) k = map[k];
if (b[j] == b[k]) k++;
}
// Phase 2: use these references while iterating over A
k = 0;
for (let i = startA; i < a.length; i++) {
while (k > 0 && a[i] != b[k]) k = map[k];
if (a[i] == b[k]) k++;
}
return k;
}
console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7
虽然有嵌套的 while 循环，但这些循环的总迭代次数不超过 n。这是因为k的值在while体内严格递减，不能变成负数。只有当 k++ 被执行了那么多次以便为此类减少提供足够的空间时，才会发生这种情况。所以总而言之，while 主体的执行次数不能超过 k++ 的执行次数，而后者显然是 O(n).
要完成，您可以在此处找到与上面相同的代码，但在交互式代码段中：您可以输入自己的字符串并以交互式方式查看结果：
function overlapCount(a, b) {
// Deal with cases where the strings differ in length
let startA = 0;
if (a.length > b.length) startA = a.length - b.length;
let endB = b.length;
if (a.length < b.length) endB = a.length;
// Create a back-reference for each index
// that should be followed in case of a mismatch.
// We only need B to make these references:
let map = Array(endB);
let k = 0; // Index that lags behind j
map[0] = 0;
for (let j = 1; j < endB; j++) {
if (b[j] == b[k]) {
map[j] = map[k]; // skip over the same character (optional optimisation)
} else {
map[j] = k;
}
while (k > 0 && b[j] != b[k]) k = map[k];
if (b[j] == b[k]) k++;
}
// Phase 2: use these references while iterating over A
k = 0;
for (let i = startA; i < a.length; i++) {
while (k > 0 && a[i] != b[k]) k = map[k];
if (a[i] == b[k]) k++;
}
return k;
}
// I/O handling
let [inputA, inputB] = document.querySelectorAll("input");
let output = document.querySelector("pre");
function refresh() {
let a = inputA.value;
let b = inputB.value;
let count = overlapCount(a, b);
let padding = a.length - count;
// Apply some HTML formatting to highlight the overlap:
if (count) {
a = a.slice(0, -count) + "<b>" + a.slice(-count) + "</b>";
b = "<b>" + b.slice(0, count) + "</b>" + b.slice(count);
}
output.innerHTML = count + " overlapping characters:\n" +
a + "\n" +
" ".repeat(padding) + b;
}
document.addEventListener("input", refresh);
refresh();
body { font-family: monospace }
b { background:yellow }
input { width: 90% }
a: <input value="acacaacaa"><br>
b: <input value="acaacaacd"><br>
<pre></pre>
我需要找到一个有效的（伪）代码来解决以下问题：
给定两个（不一定不同）整数序列 (a[1], a[2], ..., a[n]) 和 (b[1], b[2], ..., b[n])，找到最大值 d 使得 a[n-d+1] == b[1], a[n-d+2] == b[2], . ..，和 a[n] == b[d].
这不是作业，我实际上是在尝试沿尽可能多的维度收缩两个张量时想到的。我怀疑存在一个有效的算法（也许 O(n)？），但我想不出不是 O(n^2) 的东西。 O(n^2) 方法将是 d 上的明显循环，然后是项目上的内部循环以检查所需条件，直到达到最大值 d。但我怀疑可能会有比这更好的东西。
对于 O(n) time/space 复杂度，诀窍是评估每个子序列的哈希值。考虑数组 b:
[b1 b2 b3 ... bn]
使用Horner's method，您可以评估每个子序列的所有可能哈希值。选择一个基值 B（大于两个数组中的任何值）：
from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n
请注意，您可以使用前一个序列的结果在 O(1) 时间内评估每个序列，因此所有作业的成本为 O(n)。
现在你有一个数组 Hb = [h(b1), h(b2), ... , h(bn)]，其中 Hb[i] 是从 b1 到 bi.
对数组 a 做同样的事情，但有一个小技巧：
from an to an = (an * B^1)
from an-1 to an = (an-1 * B^1) + (an * B^2)
from an-2 to an = (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an = (a1 * B^1) + (a2 * B^2) + (a3 * B^3) + ... + (an * B^n)
您必须注意，当您从一个序列步进到另一个序列时，您将整个前一个序列乘以 B，然后加上乘以 B 的新值。例如：
from an to an = (an * B^1)
for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2)
hence:
from an-1 to an = (an-1 * B^1) + (an * B^2)
现在你有一个数组 Ha = [h(an), h(an-1), ... , h(a1)]，其中 Ha[i] 是从 ai 到 an.
现在，您可以比较 Ha[d] == Hb[d] 从 n 到 1 的所有 d 值，如果它们匹配，您就有答案了。
ATTENTION: this is a hash method, the values can be large and you may have to use a fast exponentiation method and modular arithmetics, which may (hardly) give you collisions, making this method not totally safe. A good practice is to pick a base
Bas a really big prime number (at least bigger than the biggest value in your arrays). You should also be careful as the limits of the numbers may overflow at each step, so you'll have to use (moduloK) in each operation (whereKcan be a prime bigger thanB).
这意味着两个不同的序列可能具有相同的散列值，但是两个相等的序列总是具有相同的散列值。
您可以利用 z algorithm 线性时间 (O(n)) 算法：
Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from S[i] which is also a prefix of S
您需要将您的数组 (b+a) 和 运行 算法连接到生成的构造数组上，直到第一个 i 这样 Z[i]+i == m+n.
例如，对于 a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0]，串联将是 [2, 3, 6, 2, 1, 0, 1, 2, 3, 6, 2, 3]，这将产生 Z[ 10] = 2 满足 Z[i] + i = 12 = m + n.
这确实可以在线性时间内完成，O(n)，并且 O(n) 额外 space .我假设输入数组是字符串，但这不是必需的。
一个朴素的方法——在匹配 k 个相等的字符后——找到一个不匹配的字符，然后返回 k-1 单位 a，重置 b 中的索引，然后从那里开始匹配过程。这显然代表了 O(n²) 最坏的情况。
为了避免这种回溯过程，我们可以观察到，如果我们在扫描最后的 k-1 个字符时没有遇到 b[0] 字符，则回溯是没有用的。如果我们 did 找到那个字符，那么回溯到那个位置只会有用，如果在那个 k 大小的子字符串中我们有一个周期性的重复。
例如，如果我们查看 a 中某处的子字符串 "abcabc"，而 b 是 "abcabd" , 并且我们发现 b 的最后一个字符不匹配，我们必须考虑到一个成功的匹配可能从子字符串中的第二个 "a" 开始，我们应该移动我们的b 中的当前索引在继续比较之前相应地返回。
然后我们的想法是根据字符串 b 进行一些预处理，以在 b 中记录反向引用，这有助于检查何时有一个不匹配。因此，例如，如果 b 是 "acaacaacd"，我们可以识别这些基于 0 的反向引用（放在每个字符下方）：
index: 0 1 2 3 4 5 6 7 8
b: a c a a c a a c d
ref: 0 0 0 1 0 0 1 0 5
例如，如果 a 等于 "acaacaaca"，则第一个不匹配发生在最后一个字符上。上面的信息然后告诉算法返回 b 到索引 5，因为 "acaac" 是常见的。然后只需更改 b 中的当前索引，我们就可以在 a 的当前索引处继续匹配。在此示例中，最后一个字符的匹配成功。
这样我们就可以优化搜索，确保a中的索引总能向前推进。
下面是 JavaScript 中该想法的实现，仅使用该语言的最基本语法：
function overlapCount(a, b) {
// Deal with cases where the strings differ in length
let startA = 0;
if (a.length > b.length) startA = a.length - b.length;
let endB = b.length;
if (a.length < b.length) endB = a.length;
// Create a back-reference for each index
// that should be followed in case of a mismatch.
// We only need B to make these references:
let map = Array(endB);
let k = 0; // Index that lags behind j
map[0] = 0;
for (let j = 1; j < endB; j++) {
if (b[j] == b[k]) {
map[j] = map[k]; // skip over the same character (optional optimisation)
} else {
map[j] = k;
}
while (k > 0 && b[j] != b[k]) k = map[k];
if (b[j] == b[k]) k++;
}
// Phase 2: use these references while iterating over A
k = 0;
for (let i = startA; i < a.length; i++) {
while (k > 0 && a[i] != b[k]) k = map[k];
if (a[i] == b[k]) k++;
}
return k;
}
console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7
虽然有嵌套的 while 循环，但这些循环的总迭代次数不超过 n。这是因为k的值在while体内严格递减，不能变成负数。只有当 k++ 被执行了那么多次以便为此类减少提供足够的空间时，才会发生这种情况。所以总而言之，while 主体的执行次数不能超过 k++ 的执行次数，而后者显然是 O(n).
要完成，您可以在此处找到与上面相同的代码，但在交互式代码段中：您可以输入自己的字符串并以交互式方式查看结果：
function overlapCount(a, b) {
// Deal with cases where the strings differ in length
let startA = 0;
if (a.length > b.length) startA = a.length - b.length;
let endB = b.length;
if (a.length < b.length) endB = a.length;
// Create a back-reference for each index
// that should be followed in case of a mismatch.
// We only need B to make these references:
let map = Array(endB);
let k = 0; // Index that lags behind j
map[0] = 0;
for (let j = 1; j < endB; j++) {
if (b[j] == b[k]) {
map[j] = map[k]; // skip over the same character (optional optimisation)
} else {
map[j] = k;
}
while (k > 0 && b[j] != b[k]) k = map[k];
if (b[j] == b[k]) k++;
}
// Phase 2: use these references while iterating over A
k = 0;
for (let i = startA; i < a.length; i++) {
while (k > 0 && a[i] != b[k]) k = map[k];
if (a[i] == b[k]) k++;
}
return k;
}
// I/O handling
let [inputA, inputB] = document.querySelectorAll("input");
let output = document.querySelector("pre");
function refresh() {
let a = inputA.value;
let b = inputB.value;
let count = overlapCount(a, b);
let padding = a.length - count;
// Apply some HTML formatting to highlight the overlap:
if (count) {
a = a.slice(0, -count) + "<b>" + a.slice(-count) + "</b>";
b = "<b>" + b.slice(0, count) + "</b>" + b.slice(count);
}
output.innerHTML = count + " overlapping characters:\n" +
a + "\n" +
" ".repeat(padding) + b;
}
document.addEventListener("input", refresh);
refresh();
body { font-family: monospace }
b { background:yellow }
input { width: 90% }
a: <input value="acacaacaa"><br>
b: <input value="acaacaacd"><br>
<pre></pre>