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

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 算法，一种线性时间 ( O (n) ) 算法：

给定一个长度为 n的字符串S，Z 算法生成一个数组Z ，其中Z[i]是从S[i]开始的最长子字符串的长度， 它也是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。