python3 lcs 最大公共子序列

时间：2023-03-10 06:21:55
python3 lcs 最大公共子序列

抛出问题：

　　假定字符串 s1 = 'BDCABA', s2 = 'ABCBDAB',求s1和s2的最大公共子序列。

问题分析：

　　我们想要求出s1和s2的最大公共子序列，我们可以用c(i,j)表示s1（i）和s2（j）最大公共子序列的长度，

　  假定c(i,j) = m,

     如果：s1[ i ]和s2[ j ]相等，那么推出c(i,j) = c(i-1,j-1)  + 1，

　 如果：s1[ i ] 和 s2[ j ]不相等,那么得到c(i,j) = max(c(i,j-1),c(i-1,j))

　 总结为公式就是：

python3 lcs 最大公共子序列

画成表格更清楚，也就是如下图，表格的数即为当前的最大公共子序列的值，箭头即为该结果是怎么得来的

例如第5行，第5列，因为第5列的c和第5行c相等，所以就等于，第4行，第4列的值+1等到2

python3 lcs 最大公共子序列

　　得到了这个值列表，就可以通过回溯的方法，从最后一个值，倒着按照箭头的方向，依次记录每个相等的值（也就是方向是左上的值），得到的结果就是我们要求的最终结果

代码实现：

# -*- coding:utf-8  -*-

# 日期：2018/6/9 15:44

# Author:小鼠标

# 求最长公共子序列

from numpy import *

s1 = 'BDCABA'

s2 = 'ABCBDAB'

def val_list(s1,s2):

    # 两个字符串的长度

    len_s1 = len(s1) + 1

    len_s2 = len(s2) + 1

    # 方向列表

    direction_list = []

    # 生成len_s2+1行len_s1+1列的全0列表

    res = zeros((len_s2,len_s1))

    direction = zeros((len_s2,len_s1))

    # print(res_list)

    for i in range(0, len_s2-1):

        for j in range(0, len_s1-1):

            #判断是否相等

            if s1[j] == s2[i]:

                res[i + 1, j + 1] = res[i, j] + 1

                # 1左上 2 上 3左

                direction[i + 1, j + 1] = 1

            else:

                if res[i + 1, j] > res[i, j + 1]:

                    res[i + 1, j + 1] = res[i + 1, j]

                    direction[i + 1, j + 1] = 3

                else:

                    res[i + 1, j + 1] = res[i, j + 1]

                    direction[i + 1, j + 1] = 2

    return res,direction

res ,direction= val_list(s1,s2)

#方向列表 1左上 2 上 3左

# [[0. 0. 0. 0. 0. 0. 0.]

#  [0. 2. 2. 2. 1. 3. 1.]

#  [0. 1. 3. 3. 2. 1. 3.]

#  [0. 2. 2. 1. 3. 2. 2.]

#  [0. 1. 2. 2. 2. 1. 3.]

#  [0. 2. 1. 2. 2. 2. 2.]

#  [0. 2. 2. 2. 1. 2. 1.]

#  [0. 1. 2. 2. 2. 1. 2.]]

#最大子序列的值列表

# [[0. 0. 0. 0. 0. 0. 0.]

# [0. 0. 0. 0. 1. 1. 1.]

# [0. 1. 1. 1. 1. 2. 2.]

# [0. 1. 1. 2. 2. 2. 2.]

# [0. 1. 1. 2. 2. 3. 3.]

# [0. 1. 2. 2. 2. 3. 3.]

# [0. 1. 2. 2. 3. 3. 4.]

# [0. 1. 2. 2. 3. 4. 4.]]

#回溯 递归求出结果

global s_res

s_res = ''

def Lcs_fun(s,res_list,i,j):

    if res_list[i,j] == 3:

        Lcs_fun(s,res_list,i,j-1)

    elif res_list[i,j] == 2:

        Lcs_fun(s,res_list,i-1,j)

    elif res_list[i,j] == 1:

        Lcs_fun(s,res_list,i-1,j-1)

        global s_res

        s_res += s[i-1]

    else:

        return

Lcs_fun(s2,direction,len(s2),len(s1))

print(s_res)

这块很容易就看晕了，仔细看，应该能看懂

相关文章