序列间重叠的高效计算

Question

给定两个序列s1和s2,s1和s2的超序列是另一个长度小于s1和s2长度之和且包含它们的序列。例如，对于s1=[1,2,4,4]和s2=[4,4,9,7]，一个超序列可以是[1,2,4,4,9,7]，也可以是[1,2,4,4,4,9,7]。

我试图找到一个函数f的有效实现，其输入是两个序列s1和s2，并做以下操作:首先，计算可能的超序列的数量，然后返回重叠发生的位置(为了简单起见，让我们假设s1总是首先出现在超序列中)。

例如，以前面的示例为例，f([1,2,4,4], [4,4,9,7])应该返回2和3，它们是两个现有超序列中第二个序列开始的索引。

Answer 1

您可以通过基于左侧列表枚举的列表推导来获得潜在的重叠位置。

idx = [ i for i,v1 in enumerate(s1) if v1==s2[0] ]
# [2, 3]

但是，我建议使用一种不同的总体策略，即使用递归生成器生成所有的超序列。

def superpose(s1,s2,inverted=False):
if s1 and not inverted and s1[0] in s2:
yield from superpose(s2,s1,True)
if not s2: return
if inverted and s2[0] not in s1:
yield s1+s2;return
for i,v1 in enumerate(s1):
if v1 != s2[0]: continue
yield from (s1[:i+1] + sp for sp in superpose(s1[i+1:],s2[1:],True))

输出:

s1=[1,2,4,4]
s2=[4,4,9,7]
for sp in superpose(s1,s2): print(sp)
[1, 2, 4, 4, 9, 7]
[1, 2, 4, 4, 4, 9, 7]
for sp in superpose(s2,s1): print(sp) # insensitive to parameter order
[1, 2, 4, 4, 9, 7]
[1, 2, 4, 4, 4, 9, 7]
s1 = [1,2,3]
s2 = [2,4,1,6,2]
for sp in superpose(s1,s2): print(sp)
[1, 2, 3, 4, 1, 6, 2]
[2, 4, 1, 6, 2, 3]

如果你需要找到最短的一个，生成器可以很容易地馈送到min函数:

min(superpose(s1,s2),key=len)    
[1, 2, 4, 4, 9, 7]

Answer 2

我想不出比这更简单的解决办法了:

def f(s1, s2):
indexes = []
for i in range(len(s1)):
seq_len = len(s1) - I
if seq_len < len(s2) and s1[i:] == s2[:seq_len]:
indexes.append(i)
return indexes

和一行，如果你喜欢生活在边缘:

indexes = [i for i in range(len(s1)) if len(s1)-i>len(s2) and s1[i:]==s2[:len(s1)-i]]