欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【动态规划】最长公共子序列和最长公共子串(python)

程序员文章站 2024-02-28 21:48:52
...

编写用时:2020年3月12日12:02:28~1h
动态规划经典例题——最长公共子序列和最长公共子串(python)
很久之前大概是高中的时候写过这种题目,使用动态规划的方法求解的,现读研究生了,要把过去的拾起来的呢。

1. 最长公共子序列(LCS)

1.1 问题描述

【动态规划】最长公共子序列和最长公共子串(python)

1.2 思路

利用动态规划。
【动态规划】最长公共子序列和最长公共子串(python)
下一步就要找到状态之间的转换方程。
【动态规划】最长公共子序列和最长公共子串(python)
因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
【动态规划】最长公共子序列和最长公共子串(python)

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)] 
     #python 初始化二维数组 [len2+1],[len1+1]
    for i in range(1,len2+1):  #开始从1开始,到len2+1结束
        for j in range(1,len1+1):  #开始从1开始,到len2+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]  #返回res[len2+1][len1+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 找到具体的子序列

下面的内容借鉴了博主Running07的博客动态规划 最长公共子序列 过程图解
如果有两个字符串如下:
S1 = “123456778”
S2 = “357486782”
其最终的动态规划填表结果为:
【动态规划】最长公共子序列和最长公共子串(python)
其中S1和S2的LCS并不是只有1个。
我们根据递归公式:

构建了上表,
通过递推公式,可以看出,res[i][j]的值来源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的较大值(可能相等)。
我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
res[8][9] = 5,且S1[8] != S2[9],所以倒推回去,res[8][9]的值来源于c[8][8]的值(因为res[8][8] > res[7][9])。
res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,res[8][8]的值来源于 res[7][7]。
以此类推,如果遇到S1[i] != S2[j] ,且res[i-1][j] = res[i][j-1] 这种存在分支的情况,这里都选择一个方向(之后遇到这样的情况,也选择相同的方向,要么都往左,要么都往上)。
【动态规划】最长公共子序列和最长公共子串(python)

可得S1和S2的LCS为{3、5、7、7、8} 这是遇见相等的时候,统一往左走
S1和S2之间还有一个LCS 这是遇见相等的时候,统一往上走:
【动态规划】最长公共子序列和最长公共子串(python)
可得S1和S2的LCS为{3、4、6、7、8}

def LCS(string1,string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1+1)] for j in range(len2+1)]  #python 初始化二维数组 [len1+1],[len2+1]
    for i in range(1,len2+1):  #开始从1开始,到len2+1结束
        for j in range(1,len1+1):  #开始从1开始,到len2+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])
    string=""  
    i=len(string2);
    j=len(string1);
    while (i > 0) & (j > 0):  #一开始我不知道加()逻辑错误
        #开始从1开始,到len2+1结束
        print(i,j)
        if string2[i-1] == string1[j-1]:
            string=string+string2[i-1]
            i=i-1
            j=j-1
        else:
            if res[i-1][j]>res[i][j-1]:
                i=i-1
            elif res[i-1][j]<res[i][j-1]:
                j=j-1
            else:
                i=i-1
    return res,res[-1][-1],string[::-1]  # 倒序输出
print(LCS("helloworld","loop"))

输出:
4 10
3 10
3 9
3 8
3 7
2 6
2 5
1 4
([[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, 'loo')

2. 最长公共子串

2.1 问题描述

【动态规划】最长公共子序列和最长公共子串(python)

2.2 思路

和最长公共子序列一样,使用动态规划的算法。
【动态规划】最长公共子序列和最长公共子串(python)
下一步就要找到状态之间的转换方程。
和LCS问题唯一不同的地方在于当A[i] != B[j]时,res[i][j]就直接等于0了,因为子串必须连续,且res[i][j] 表示的是以A[i],B[j]截尾的公共子串的长度。因此可以根据这个方程来进行填表,以"helloworld"和“loop”为例:
【动态规划】最长公共子序列和最长公共子串(python)
这个和LCS问题还有一点不同的就是,需要设置一个result,每一步都更新得到最长公共子串的长度。

2.3 Python代码

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

2.4 返回子串

def LCS(string1,string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1+1)] for j in range(len2+1)]  #python 初始化二维数组 [len1+1],[len2+1]
    result =0
    index=0
    for i in range(1,len2+1):  #开始从1开始,到len2+1结束
        for j in range(1,len1+1):  #开始从1开始,到len2+1结束
            if string2[i-1] == string1[j-1]:
                res[i][j] = res[i-1][j-1]+1
                if result<res[i][j]:
                    index=i
                result = max(res[i][j],result)         
    string=string2[index-result:index] 
   
    return res,result,string  # 输出
print(LCS("hellooxworld","looxoxp"))

([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 3, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], 
4, 'loox')
相关标签: 面试准备