最长公共子序列python实现

系统 131 0

最长公共子序列python实现

1、dp基本思路:

公共子序列最优子结构:
将问题分解表成更简单的子问题,这个子问题可以分解成更多的子问题使用动态规划算法求解,这个过程需要在一个表中储存同一级别的子问题的解,因此这个解可以被更高级的子问题使用。

2、问题的解

定义两个序列X、Y,二维数组f[i][j]表示X的i位和Y的j位之前的最长公共子序列长度,
则有
 f[1][1] = same(1,1)
 f[i][j] = max(f[i-1][j-1]+same(i,j),f[i-1][j],f[i][j-1)

其中same(i,j)表示X[i]==Y[j]
 same(a,b)当X的第a位于Y的第b位完全相同时为1,否则为0
 此时,f[i][j]中最大的数便是 X和 Y的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。

如:

X = 'helloword'
Y = 'eoskod'

X,Y的最长公共子序列长度为4,最长公共子序列为'eood'

该算法的空间、时间复杂度均为O(n^2)} O(n^2)。经过优化后,空间复杂度可为 O(n),时间复杂度可为O(nlogn)。
注:最长公共子序列不要求序列连续

python代码:

            
              UP_LEFT = 0		#左上
UP = 1			#上
LEFT = 2		#左

def LCSlength(X,Y):
    '''
    输入:序列X和序列Y
    输出:X和Y的最长公共子序列长度
    '''
    #定义f数组,每行n个元素,每列m个元素
    m = len(X)
    n = len(Y)
    #lf = (lambda x,y:x+1 if x>y else y+1)
    #size = lf(m,n)
    f = [[0 for x in range(n+1)] for y in range(m+1)]
    #定义路径数组
    path = [[-1 for x in range(n+1)] for y in range(m+1)]

    for i in range(1,m+1):
        for j in range(1,n+1):
            if(X[i-1] == Y[j-1]):
               f[i][j] = f[i-1][j-1]+1
               path[i][j] = UP_LEFT
            else:
               #f[i][j] = max(f[i-1][j],f[i][j-1])
                if(f[i-1][j]>f[i][j-1]):
                    f[i][j] = f[i-1][j]
                    path[i][j] = UP
                else:
                    f[i][j] = f[i][j-1]
                    path[i][j] = LEFT
    return f[m][n],path

def getpath(path,X,i,j,arr):
    '''
        回溯求子序列
        输入:path,二维数组,路径信息
            X,原始序列
            i,j ,递归下标
            arr,存储结果元素
    '''
    if(i==0 or j ==0):
        return
    elif(path[i][j] == UP_LEFT):
        getpath(path,X,i-1,j-1,arr)
        arr.append(X[i-1])
    elif(path[i][j]==UP):
        getpath(path,X,i-1,j,arr)
    elif(path[i][j]==LEFT):
        getpath(path,X,i,j-1,arr)
    else:
        pass
        

X=[1,3,1,4,5]
Y=[1,1,1,4,5]

#X = 'helloword'
#Y = 'eoskod'
    
arr = []
length,path = LCSlength(X,Y)
getpath(path,X,len(X),len(Y),arr)
print(length)
print(arr)
            
          

看到网上还有将之转化成最长上升序列算法求解,思路是转化为最长上升子序列,并采用二分搜索,这种方法可以把平均时间复杂度降到nlogn,但是存在极端情况效率比普通的动态规划方法效率更低。先留个坑,后再研究,睡觉zzz

参考:

https://blog.csdn.net/v_JULY_v/article/details/6110269#commentsedit

https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

发表我的评论
最新评论 总共0条评论