最长公共子序列及Python实现

1 最长公共子序列问题描述

一个给定序列的子序列是在该序列中删除若干元素后得到的序列，确切的说，若给定序列X = {x1,x2,...xm},则另一个序列，Y= {y1,y2...,yn},当另一个序列即是X的子序列又是Y的子序列时，称Z是序列X也Y的公共子序列。最长公共子序列问题为给定序列X和Y，找到所有公共子序列中最长的一个（非连续）。

2 最长公共子序列的结构

解最长公共子序列问题的最容易想到的方法是穷举法，即对X的所有子序列，检查它是否也是Y 的子序列，从而确定它是否为X和Y 的公共子序列，并且在检查过程中记录最长的公共子序列。X的所有子序列检查过后即可求出X和Y 的最长公共子序列。X的没个子序列相应于下标集{1,2....m}的一个子集。因此，公有2**m个不同的子序列，从而穷举法需要指数时间。

事实上，最长公共子序列问题具有最优子结构性质：

设序列X={x1,x2,....xm}和Y= {y1,y2...,yn}的一个最长公共子序列为Z={z1,z2,...zk}，则

(1) 若xm=yn ,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。

(2)若xm≠yn，且zk≠xm，则z是Xm-1和Y的最长公共子序列。

(3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。

证明略

3 子问题的递归结构

由最长公共子序列问题的最优子结构性质可知，要找出X={x1,x2,....xm}和Y={y1,y2...yn}的最长公共子序列，可以按照以下方式递归的进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得到X和Y的一个最长公共子序列，当xm≠yn时，必须接两个字问题，也就是要找出Xm-1和Yn的一个最长公共子序列已经Xm和Yn-1的一个最长公共子序列。并求两个子问题公共子序列最长的。用c[i][j]记录序列的Xi和Yj的最长公共子序列的长度，其中Xi={x1,x2...xi};Yj={y1,y2...yj},当i=0或j=0时，空序列是Xi和Yj的最长公共子序列故此时c[i][j]=0,由最优子结构性质可建立递归关系如下：

4 计算最优值

直接利用递归关系式容易写出一个计算c[i][j]的递归算法，但其计算时间是随输入长度指数增长的，由于在考虑的子问题空间中，总共有Φ(mn)个不同的子问题，因此，用动态规划算法由底向上计算最优值能提高算法的效率。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+vMbL49fus6S5q7my19PQ8sHQs6S2yLXEtq/MrLnmu67L47eoTENTTGVuZ3Ro0tTQ8sHQWD17eDEseDIuLi54bX26zVk9e3kxLHkyLi4ueW591+7OqsrkyOujrMrutNnBvbj2yv3X6WO6zWKjrMbk1tBjW2ldW2pdtOa0olhpus1ZarXE1+6zpLmrubLX09DywdC1xLXEs6S2yKOsYltpXVtqXbzHwrxjW2ldW2pdtcQmIzIwNTQwO8rH08nExNK7uPbX087KzOK94r72tcO1vbXEoaO+38zltPrC68q1z9bI58/Co6hweXRob26jqTwvcD4KPHByZSBjbGFzcz0="brush:java;">def LCSLength(m, n, x=None, y=None,c=None, b=None): for i in range(1, m): for j in range(1, n): if x[i-1] == y[j-1]: c[i][j] = c[i-1][j-1]+1 b[i][j] = 'equals' elif c[i-1][j] >= c[i][j-1]: c[i][j] = c[i-1][j] b[i][j] = 'up' else: c[i][j] = c[i][j-1] b[i][j] = 'left'

5 构造最长公共子序列

由算法LCSLength计算得到的数组b可用于快速构造序列X={x1,x2...xm}和Y={y1,y2...yn}的最长公共子序列。首先从b[m][n]开始，根据b[i][j]值所指向的方向进行搜索。equals表示等于，即X和Y的最长公共子序列为Xi-1和Yj-1的最长公共子序列加上xi所得的最长公共子序列，left为向左，即Xi和Yj的最长公共子序列与Xi和Yj的最长公共子序列相同，up表示向上，即Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。下面LCS算法为具体的求解过程。

def GetLCS(i, j, x=None, b=None):
    if i == 0 and j == 0:
        return
    if b[i][j] == 'equals':
        GetLCS(i-1,j-1, x, b)
        print x[i-1], ' '
    elif b[i][j] == 'left':
        GetLCS(i, j-1, x, b)
    else:
        GetLCS(i-1, j, x, b)

6 实例分析

现有两个序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，由算法LCSLength和LCS计算出的结果如图所示：

7 代码运行实现

#-*-coding:utf8-*-
"""

Author  : xianghonglee
Email   : xianghongleeking@gmail.com
Created on '14-5-26'
"""

def LCSLength(m, n, x=None, y=None,c=None, b=None):
    for i in range(1, m):
        for j in range(1, n):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i-1][j-1]+1
                b[i][j] = 'equals'
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 'up'
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = 'left'

def GetLCS(i, j, x=None, b=None):
    if i == 0 and j == 0:
        return
    if b[i][j] == 'equals':
        GetLCS(i-1,j-1, x, b)
        print x[i-1], ' '
    elif b[i][j] == 'left':
        GetLCS(i, j-1, x, b)
    else:
        GetLCS(i-1, j, x, b)


if __name__ == '__main__':
    x ="ABCBDAB"
    y = "BDCABA"
    m = len(x)+1
    n = len(y)+1
    b = [[0 for i in range(n)] for j in range(m)]
    c = [[0 for i in range(n)] for j in range(m)]

    LCSLength(m,n,x,y,c,b)
    for i in c:
        print i
    for j in b:
        print j
    GetLCS(m-1,n-1,x,b)

打印结果为：