python - 许多子序列之间的最长公共(public)序列

Question

有趣的标题:) 我有一个包含以下内容的文件:

>sequence_40
ABCDABDCABCDBACDBACDBACDBACDABDCDC
ACDCCDCABDCADCADBCACBDCABD
>sequence_41
DCBACDBACDADCDCDCABCDCACBDCBDACBDC
BCDBABABBABACDCDBCACDBACDBACDBACDC
BCDB
...

然后，我有一个函数返回一个字典(称为 dict)，该字典返回序列作为键，字符串(组合在一行)作为键的值。序列范围为 40 至 59。 我想获取序列字典并返回所有序列中找到的最长公共(public)子序列。设法在 stackoverflow 上找到一些帮助，并编写了一个代码，仅比较该字典中的最后两个字符串，而不是全部:)。 这是代码

def longest_common_sequence(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

for i in range(40,59):
    s1=str(dictionar['sequence_'+str(i)])
    s2=str(dictionar['sequence_'+str(i+1)])
longest_common_sequence(s1,s2)

如何修改它以获得字典中所有序列之间的公共(public)子序列？谢谢!

Answer 1

编辑:正如@lmcarreiro指出的，子字符串(或子数组或子列表)和子序列之间存在相关差异。据我了解，我们在这里都在谈论子字符串，因此我将在回答中使用这个术语。

纪尧姆的回答可以改进:

def eachPossibleSubstring(string):
  for size in range(len(string) + 1, 0, -1):
    for start in range(len(string) - size + 1):
      yield string[start:start+size]

def findLongestCommonSubstring(strings):
  shortestString = min(strings, key=len)
  for substring in eachPossibleSubstring(shortestString):
    if all(substring in string
        for string in strings if string != shortestString):
      return substring

print findLongestCommonSubstring([
  'ABCDABDCABCDBACDBACDBACDBACDABDCDCACDCCDCABDCADCADBCACBDCABD',
  'DCBACDBACDADCDCDCABCDCACBDCBDACBDCBCDBABABBABACDCDBCACDBACDBACDBACDCBCDB',
])

打印:

ACDBACDBACDBACD

这更快，因为我返回第一个找到的内容并从最长到最短进行搜索。

基本思想是这样的:取出最短字符串中的每个可能的子字符串(按照从最长到最短的顺序)，然​​后看看是否可以在所有其他字符串中找到该子字符串。如果是，则返回它，否则尝试下一个子字符串。

您需要了解生成器。尝试 e。 G。这个:

for substring in eachPossibleSubstring('abcd'):
  print substring

或

print list(eachPossibleSubstring('abcd'))