1. 最长公共子序列（LCS）
1.1 问题描述
1.2 思路
利用动态规划。
下一步就要找到状态之间的转换方程。
因此可以根据这个方程来进行填表，以"helloworld"和“loop”为例：
1.3 Python代码
def LCS(string1,string2):
len1 = len(string1)
len2 = len(string2)
res = [[0 for i in range(len1+1)] for j in range(len2+1)]
for i in range(1,len2+1):
for j in range(1,len1+1):
if string2[i-1] == string1[j-1]:
res[i][j] = res[i-1][j-1]+1
else:
res[i][j] = max(res[i-1][j],res[i][j-1])
return res,res[-1][-1]
print(LCS("helloworld","loop"))
# 输出结果为：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3],
[0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3]], 3
所以"helloworld"和"loop"的最长公共子序列的长度为3。
1.4 找到具体的子序列
具体请参考https://blog.csdn.net/ggdhs/article/details/90713154
- 最长公共子串
- 1 问题描述
2.2 思路
和最长公共子序列一样，使用动态规划的算法。
下一步就要找到状态之间的转换方程。
和LCS问题唯一不同的地方在于当A[i] != B[j]时，res[i][j]就直接等于0了，因为子串必须连续，且res[i][j] 表示的是以A[i]，B[j]截尾的公共子串的长度。因此可以根据这个方程来进行填表，以"helloworld"和“loop”为例：
这个和LCS问题还有一点不同的就是，需要设置一个res，每一步都更新得到最长公共子串的长度。
def LCstring(string1,string2):
len1 = len(string1)
len2 = len(string2)
res = [[0 for i in range(len1+1)] for j in range(len2+1)]
result = 0
for i in range(1,len2+1):
for j in range(1,len1+1):
if string2[i-1] == string1[j-1]:
res[i][j] = res[i-1][j-1]+1
result = max(result,res[i][j])
return result
print(LCstring("helloworld","loop"))
# 输出结果为：2
京公网安备 11010502036488号