使用Python3得到两个字符串的最长公共子序列
使用动态规划的方法：
def find_lc(str1:str,str2:str):
"""
找到str1和str2之间的最长子字符串，返回其长度和该字符串
"""
m = [ [ 0 for _ in range(len(str2)+1) ] for _ in range(len(str1)+1) ] #长度
d = [ [ for _ in range(len(str2)+1) ] for _ in range(len(str1)+1) ] #子字符串
for p1 in range(len(str1)):
for p2 in range(len(str2)):
if str1[p1]==str2[p2]:
m[p1+1][p2+1]=m[p1][p2]+1
d[p1+1][p2+1]=d[p1][p2]+str1[p1]
elif m[p1+1][p2]>m[p1][p2+1]:
m[p1+1][p2+1]=m[p1+1][p2]
d[p1+1][p2+1]=d[p1+1][p2]
else:
m[p1+1][p2+1]=m[p1][p2+1]
d[p1+1][p2+1]=d[p1][p2+1]
return (m[len(str1)][len(str2)],d[len(str1)][len(str2)])
示例：
print(find_lc(abdfg,abcdfg))
输出结果：
(5, ‘abdfg’)
参考资料：
- 这一篇使用的还是Python2。
- 这一篇中还介绍了除动态规划外其他的方法。囿于时间所限我就只写了一种方法，其他方法以后有时间了再来补。
