我一直在使用最长公共子序列(LCS)来查找序列之间的相似性。以下动态规划代码计算答案。
def lcs(a, b):
lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
# row 0 and column 0 are initialized to 0 already
for i, x in enumerate(a):
for j, y in enumerate(b):
if x == y:
lengths[i+1][j+1] = lengths[i][j] + 1
else:
lengths[i+1][j+1] = \
max(lengths[i+1][j], lengths[i][j+1])
# read the substring out from the matrix
result = ""
x, y = len(a), len(b)
while x != 0 and y != 0:
if lengths[x][y] == lengths[x-1][y]:
x -= 1
elif lengths[x][y] == lengths[x][y-1]:
y -= 1
else:
assert a[x-1] == b[y-1]
result = a[x-1] + result
x -= 1
y -= 1
return result
然而,我意识到我真正想解决的问题有些不同。给定一个固定的 k,我需要确保公共子序列仅涉及长度恰好为 k 的子字符串。例如,设 k = 2,让这两个字符串为
A = "abcbabab"
B = "baababcc"
我需要的子序列是 "
ba"+"ab" = baab
。是否可以修改动态规划解决方案来解决这个问题?
原始的最长公共子序列问题只是 k=1 的情况。 一个不起作用的方法。 如果我们执行上面的LCS算法,我们可以从动态规划表中得到对齐,并检查这些符号是否出现在两个输入序列的长度为k的非重叠子字符串中,如果没有,则删除它们。问题是这并不能给出最优解。
aaa
,当k=2
时,最长子序列应该是aa
,对吗?(如果不是,那么在aaa_bc_bc
和bc:bc:aaa
中最长的序列是什么?) - amit