验证中...
码云 Gitee IDE 全新上线——支持 Git 管理的轻量在线编码环境
语言: Python
分类: 算法分析
最后更新于 2018-10-12 00:20
gistfile1.txt
原始数据 复制代码
#最长公共子序列
def longest_common_subsequence(x, y):
n = len(x)
m = len(y)
A = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
for j in range(m):
if x[i] == y[j]:
A[i+1][j+1] = A[i][j]+1
else:
A[i+1][j+1] = max(A[i][j+1],A[i+1][j])
sol = []
i, j = n, m
while A[i][j] >0:
if A[i][j]==A[i-1][j]:
i -= 1
elif A[i][j]==A[i][j-1]:
j -= 1
else:
i -= 1
j -= 1
sol.append(x[i])
return ''.join(sol[::-1])
if __name__ == '__main__':
s = 'Google,Microsoft, PyThon, Cplusplis'
t = 'OOgle,Cplusplus'
print(longest_common_subsequence(s, t))

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助