python公共子序列
时间: 2023-11-06 19:02:51 浏览: 39
最长公共子序列问题是求解两个字符串中最长的公共子序列的长度。解决这个问题可以使用动态规划的方法。定义一个二维数组dp,其中dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。根据动态规划的思想,可以得到如下的状态转移方程:
- 当A[i]等于B[j]时,即字符串A的第i个字符和字符串B的第j个字符相等时,dp[i][j] = dp[i-1][j-1] + 1;
- 当A[i]不等于B[j]时,即字符串A的第i个字符和字符串B的第j个字符不相等时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
接下来,我们可以根据上述的状态转移方程,使用两层循环来求解最长公共子序列的长度,具体的实现代码如下:
<<引用:import numpy
def find_lcseque(s1, s2):
m = [[0 for x in range(len(s2)+1)] for y in range(len(s1)+1)]
d = [[None for x in range(len(s2)+1)] for y in range(len(s1)+1)]
for p1 in range(len(s1)):
for p2 in range(len(s2)):
if s1[p1] == s2[p2]:
m[p1+1][p2+1] = m[p1][p2] + 1
d[p1+1][p2+1] = 'ok'
elif m[p1+1][p2] > m[p1][p2+1]:
m[p1+1][p2+1] = m[p1+1][p2]
d[p1+1][p2+1] = 'left'
else:
m[p1+1][p2+1] = m[p1][p2+1]
d[p1+1][p2+1] = 'up'
(p1, p2) = (len(s1), len(s2))
s = []
while m[p1][p2]:
c = d[p1][p2]
if c == 'ok':
s.append(s1[p1-1])
p1 -= 1
p2 -= 1
if c == 'left':
p2 -= 1
if c == 'up':
p1 -= 1
s.reverse()
return ''.join(s)
print(find_lcseque('acbd', 'abedc'))>>
根据上述代码,输入的两个字符串分别是'acbd'和'abedc',输出的最长公共子序列的长度为3。