algorithm - 给定两个序列，找出一个序列的结尾和另一个序列的开头之间的最大重叠

Question

我需要找到一个有效的(伪)代码来解决以下问题:

给定两个(不一定是不同的)整数序列 (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 .但我怀疑比这更好的事情是可能的。

Answer 1

您可以使用 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。