首页 > 搜索 > 最长公共子序列算法实现代码,算法导论-动态规划(最长公共子序列问题LCS)

最长公共子序列算法实现代码,算法导论-动态规划(最长公共子序列问题LCS)

互联网 2020-10-20 16:08:18
在线算命,八字测算命理

    首先定义一个给定序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果,其形式化定义如下:给定一个序列X = ,另一个序列Z = 满足如下条件时称为X的子序列,即存在一个严格递增的X的下标序列,对于所有j = 1,2,...,k,满足xij = zj,例如,Z=是X=的子序列,对应的下标序列为。给定两个序列X和Y,如果Z是X的子序列,也是Y的子序列,则称它是X和Y的公共子序列。

   最长公共子序列问题(longest-common-subsequence problem)可用动态规划方法高效地求解。

   步骤1:刻画最长公共子序列的特征

   LCS问题具有 最优子结构性质。子问题的自然分类对应两个输入序列的“前缀"对。"前缀"的定义如下:给定一个序列X = ,对于i = 0,1,...,m,定义X的第i前缀为Xi = 。例如,若 X = ,则 X4 = ,X0为空串。

    令X = 和Y =  为两个序列,Z =为X和Y的任意LCS。

    如果Xm = Yn,则 Zk =  Xm = Yn且Zk-1 是Xm-1和Yn-1的一个LCS。    如果 Xm ≠ Yn,那么Zk ≠  Xm意味着Z是Xm-1和Y的一个LCS。    如果 Xm ≠ Yn,那么Zk ≠  Yn意味着Z是X和Yn-1的一个LCS。

    步骤2:一个递归解

    很容易看出LCS问题的重叠子问题性质。为了求X和Y的一个LCS,我们可能需要求X和Yn-1的一个LCS及Xm-1和Y的一个LCS。但是这几个子问题都包含求解Xm-1和Yn-1的LCS的子子问题。我们定义c[i,j]表示Xi和Yj的LCS的长度。如果i= 0 或j = 0,即一个序列长度为0,那么LCS的长度为0,根据LCS问题的最优子结构性质,可得如下公式:

     步骤3:计算LCS的长度

    过程LCS-LENGTH接受两个序列X = 和Y = 为输入。它将c[i,j]的值保存在表c[0...m,0...n]中,过程还维护一个表b[1...m,1...n],帮助构造最优解。b[i,j]指向的表项对应计算c[i,j]时所选择的子问题最优解。过程返回表b和表c,c[m,n]保存了X和Y的长度。

//伪代码LCS-LENGTH(X,Y)m = X.lengthn = Y.lengthlet b[1..m,1..n] and c[0..m,0..n]be new tablesfor i = 1 to m    c[i,0] = 0for j = 0 to n    c[0,j] = 0for i = 1 to m    for j = 1 to nif xi == yic[i,j] = c[i-1,j-1] + 1b[i,j] = "\"

else if c[i-1,j] ≥ c[i,j-1]

c[i,j] = c[i-1,j]

b[i,j] = "|"

else

c[i,j] = c[i,j-1]

b[i,j] = "—"

return c and b

下图显示了LCS-LENGTH对输入序列X= 和Y=生成的结果。过程的运行时间为O(mn)。

    步骤4:构造LCS

    利用LCS-LENGTH返回的表b快速构造X和Y的LCS,只需简单地从b[m,n]开始,并按箭头方向追踪下去即可。挡在表项b[i,j]中遇到一个”\"时,意味着xi=yi是LCS的一个元素。下面的递归过程会按正确的顺序打印出X和Y的一个LCS。对它的起始调用为PRINT-LCS(b,X,X.length,Y.length)。

PRINT-LCS(b,X,i,j)

if == 0 or j==0

return

if b[i,j] == "\"

PRINT-LCS(b,X,i-1,j-1)

print xi

else if b[i,j] == "|"

PRINT-LCS(b,X,i-1,j)

else

PRINT-LCS(b,X,i,j-1)

 

实现:

1 void lcsLength(string x,string y, vector< vector> &c, vector< vector> &b) 2 { 3 int m = x.size(); 4 int n = y.size(); 5 c.resize(m+1); 6 b.resize(m+1); 7 for(int i = 0; i < c.size(); ++i) 8 c[i].resize(n+1); 9 for(int i = 0; i < b.size(); ++i)10 b[i].resize(n+1);11 12 for(int i = 1; i = c[i][j-1]){18 c[i][j] = c[i-1][j];19 b[i][j] ='u';20 }else{21 c[i][j] = c[i][j-1];22 b[i][j] = 'l';23 }24 }25 }26 } 1 void print_lcs(vector< vector> &b,string x, int i, int j) 2 { 3 if(i == 0 || j == 0) 4 return; 5 if(b[i][j] == 'c'){ 6 print_lcs(b,x,i-1,j-1); 7 coutc; 6 vector< vector> b; 7 8 lcsLength(x,y,c,b); 9 print_lcs(b,x,x.size(),y.size());10 }

输出:

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多