具有固定长度子串的最长公共子序列
我一直在使用最长公共子序列（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的非重叠子串中，如果不是，则删除它们。 问题是这不能提供最佳解决方案。
更正基本上是当相关索引中的两个字符串具有匹配的子字符串（而不是现在的匹配字母）时。
这个想法不是简单地检查原始解决方案中的大小为1的子字符串，检查长度为k的子字符串，并将解决方案加1（以及在字符串中由' k '跳转''）。
应该转换为DP解决方案的递归方法的公式是：
f(i,0) = 0
f(0,j) = 0
f(i,j) = max{
f(i-k,j-k) + aux(s1,s2,i,j,k)
f(i-1,j)
f(i,j-1)
}
其中aux(s1,s2,i,j,k)是一个旨在检查两个子串是否匹配的函数，定义如下：
aux(s1,s2,i,j,k) = 1 | if s1.substring(i-k,i) equals s2.substring(j-k, j)
-infinity | otherwise
您可以稍后使用标记max{}的辅助矩阵的辅助矩阵重新构建队列，并在矩阵完成时从最后到第一个矩阵。
例：
bcbac和cbcba 。 k=2
由f生成的矩阵：
c b c b a
0 0 0 0 0 0
b 0 0 0 0 0 0
c 0 0 0 1 1 1
b 0 0 1 1 1 1
a 0 0 1 1 1 2
c 0 0 1 1 1 2
为了重现对齐，你生成'选择'矩阵：
1 - 选择f（ik，jk）+ aux（s1，s2，i，j，k）
2 - 选择f（i-1，j）
3 - 选择f（i，j-1）
d - 不在乎，（所有选择都很好）
x / y - 表示x或y中的一个。
c b c b a
b 2/3 2/3 2/3 2/3 2/3
c 2/3 2/3 1 2 2
b 2/3 3 2/3 d 2/3
a 2/3 3 2/3 2/3 1
c 2/3 3 2/3 2/3 3
现在，重建对齐 - 从最后一个（右下角）单元格开始：
重建时访问的顺序是：（0表示 - 未访问，多个单元中的数字表示这些中的任何一个都可以）。
c b c b a
0 4 0 0 0 0
b 4 3 0 0 0 0
c 0 0 0 0 0 0
b 0 0 0 2 0 0
a 0 0 0 0 0 0
c 0 0 0 0 0 1
上一篇: Longest common subsequence with fixed length substrings