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
。
是否可以修改动态规划解来解决这个问题?
当相关索引中的两个字符串有一个匹配的子字符串(而不是像现在这样的匹配字母)时,基本上就是更正。
这个想法不是简单地在原始解决方案中检查大小为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) = 1 | if s1.substring(i-k,i) equals s2.substring(j-k, j)
-infinity | otherwise
示例:
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
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
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
一个序列中去掉若干(也可以不去掉)元素剩下的部分称为其子序列。对于给定的序列X = <x1,x2,…,xm>,称序列Z = <z1,z2,…,zk>为X的一个子序列,仅当在X中存在一个递增序号序列<i1,i2,…,ik>,对所有的j(1,2,…,k)满足 xij= z j。例如,Z = <a,b,f,c>是X = <a,b,c,f,b,c> 的一个子序列,X中相应的序号序列为 <1,2,4,6>
longestCommonSubsequence正在返回LCS的长度。代码运行良好。但我试图打印子序列的值。例如,它应该打印“acef”。但我的代码只打印“ae”<如何修复? 这是完整的代码https://pastebin.com/Sq4QMtxF
我想出了一个蛮力算法来寻找两个给定字符串之间最长的公共子序列。它看起来时间复杂度为O(n^3)。它通过了我所有的测试用例,但我仍然不确定它是否会通过所有的测试用例......请让我知道这是正确的蛮力算法? 如果上面的代码不对,我要蛮力算法返回最长的公共子序列字符串,,我怎么才能做到这一点???
在最多一个序列存在重复的情况下,可以将最长公共子序列问题转化为最长递增子序列问题。减少问题的过程说明在这里: 假设您有以下序列: 然后,创建一个整数序列S3,其中您必须将S2的每个元素的位置放在S1中(如果元素在S1中不存在,那么忽略那个元素)。在本例中: 这种方法是如何工作的?为什么这种约简解决了寻找最长公共子序列的问题?
我目前正在尝试为2个给定字符串查找和打印最长的公共子序列。我使用最常见的算法,没有递归。如果我保留整个数组,这是一项简单的任务,但我正在尝试对其进行一点优化,只使用2行,您可以在下面的代码中看到。有了这个更改,查找长度仍然很简单,工作正常,但恢复子序列不再那么容易了。我尝试了几种方法,但都不起作用。下面你可以看到我最后的尝试。虽然它适用于相同的情况,但也有失败的情况。经过长时间的思考,我开始相信没
问题内容: python中是否有内置函数返回两个列表的最长公共子序列的长度? 我试图找到最长的公共子序列,然后得到它的长度,但是我认为必须有一个更好的解决方案。 问题答案: 您可以轻松地将LCS重新装配为LLCS: 演示: 如果您想要最长的公共 子字符串 (一个 不同 但相关的问题, 子 序列是连续的),请使用: 这与动态编程方法非常相似,但是我们跟踪到目前为止找到的最大长度(因为不再保证表中的最