Python中最长的公共子序列
Python中最长的公共子序列
提问于 2018-02-07 05:00:57
我正在尝试寻找两个字符串之间最长的公共子序列。
我看了这个https://www.youtube.com/watch?v=NnD96abizww教程
并写道：
# Longest Common Subsequence
def lcs(s1, s2):
matrix = [ [0 for x in range(len(s2))] for x in range(len(s1)) ]
cs = ""
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i]==s2[j]:
if i==0 or j==0:
matrix[i][j] = 1
cs += s1[i]
else:
matrix[i][j] = matrix[i-1][j-1] + 1
cs += s1[i]
else:
if i==0 or j==0:
matrix[i][j] = 0
else:
matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
return matrix[len(s1)-1][len(s2)-1], cs
print(lcs("abcdaf", "acbcf"))
I get (3, 'abccaf')这显然是错误的，它应该是4 abcf。
不确定哪一步出错了。一个普遍的问题是，程序员通常需要多长时间才能“理解”这些问题？
回答 3
Stack Overflow用户
发布于 2019-11-08 21:23:34
对于那些寻找内置解决方案的人：
from difflib import SequenceMatcher
str_a = "xBCDxFGxxxKLMx"
str_b = "aBCDeFGhijKLMn"
s = SequenceMatcher(None, str_a, str_b)
lcs = ''.join([str_a[block.a:(block.a + block.size)] for block in s.get_matching_blocks()])
# lcs = 'BCDFGKLM'Stack Overflow用户
发布于 2019-05-08 23:20:34
通过使用以下代码段获得LCS的长度，您将发现最大长度为14，因此BurningKarl的解决方案适用于我。
def longestCommonSequence(s1, s2, s1Index, s2Index, arr):
if s1Index ==-1 or s2Index == -1:
return 0
if(arr[s1Index][s2Index] != None):
return arr[s1Index][s2Index]
if s1[s1Index] == s2 [s2Index]:
result = 1+ longestCommonSequence(s1, s2, s1Index -1, s2Index -1, arr)
else:
result= max(longestCommonSequence(s1, s2, s1Index -1, s2Index, arr), longestCommonSequence(s1, s2, s1Index, s2Index -1, arr))
arr[s1Index][s2Index] = result
return result
s1="AAACCGTGAGTTATTCGTTCTAGAA"
s2="CACCCCTAAGGTACCTTTGGTTC"
a = [[None for i in range(len(s2))] for j in range(len(s1))]
print(longestCommonSequence(s1, s2, len(s1)-1, len(s2)-1, a))Stack Overflow用户
发布于 2019-09-13 01:01:37
def subrange(i, strr) :
a = i[len(i) - 1]
for j in range(len(i) - 1, len(strr)) :
if a == strr[j] :
return j
return
def subseq(strr) :
prev = [i for i in strr]
nex1 = []
nex = []
a = set()
for i in prev :
a.add(i)
while( len(prev[0])< len(strr)):
for i in prev :
for j in range(subrange(i,strr) + 1, len(strr)) :
nex.append(i + strr[j])
prev = nex
nex = []
for i in prev :
a.add(i)
return a
a1 = []
a2 = []
sol = ""
maxx = 0
str1 = input()
str2 = "sai"
if(len(str1) == 0 or len(str2) == 0) :
sol = "NULL"
else :
a1 = list(subseq(str1))
a2 = list(subseq(str2))
for i in range(0, len(a1)) :
for j in range(0, len(a2)) :
if a1[i] == a2[j] :
if len(a1[i]) > maxx :
sol = a1[i]
maxx = len(sol)
print(sol)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48651891
复制相关文章
相似问题