最长公共子序列实例_南京Java培训

　　一个字符串S,去掉零个或者多个元素所剩下的子串称为S的子序列。最长公共子序列就是寻找两个给定序列的子序列，该子序列在两个序列中以相同的顺序出现，但是不必要是连续的。

　　例如序列X=ABCBDAB,Y=BDCABA.序列BCA是X和Y的一个公共子序列，但是不是X和Y的最长公共子序列，子序列BCBA是X和Y的一个LCS,序列BDAB也是。南京Java软件培训

　　寻找LCS的一种方法是枚举X所有的子序列，然后注意检查是否是Y的子序列，并随时记录发现的最长子序列。假设X有m个元素，则X有2^m个子序列，指数级的时间，对长序列不实际。

　　使用动态规划求解这个问题，先寻找最优子结构。设X=<x1,x2,…，xm>和Y=<y1,y2,…，yn>为两个序列，LCS（X,Y）表示X和Y的一个最长公共子序列，可以看出

　　如果xm=yn,则LCS （ X,Y ） = xm + LCS （ Xm-1,Yn-1 ）。南京Java软件培训

　　如果xm!=yn,则LCS（ X,Y ）= max{ LCS （ Xm-1, Y ）， LCS （ X, Yn-1 ） }

　　LCS问题也具有重叠子问题性质：为找出X和Y的一个LCS,可能需要找X和Yn-1的一个LCS以及Xm-1和Y的一个LCS.但这两个子问题都包含着找Xm-1和Yn-1的一个LCS,等等。

　　DP最终处理的还是数值（极值做最优解），找到了最优值，就找到了最优方案；为了找到最长的LCS,我们定义dp[i][j]记录序列LCS的长度，合法状态的初始值为当序列X的长度为0或Y的长度为0,公共子序列LCS长度为0,即dp[i][j]=0,所以用i和j分别表示序列X的长度和序列Y的长度，状态转移方程为

　　dp[i][j] = 0  如果i=0或j=0 南京Java软件培训

　　dp[i][j] = dp[i-1][j-1] + 1  如果X[i-1] = Y[i-1]

　　dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }  如果X[i-1] != Y[i-1]

　　求出了最长公共子序列的长度后，输出LCS就是输出dp的最优方案了，这在01背包中已经讲过，既可以用一个额外的矩阵存储路径，也可以直接根据状态转移矩阵倒推最优方案。代码如下：

　　[cpp]

　　#include <iostream>

　　using namespace std;

　　/* LCS

　　* 设序列长度都不超过20 南京Java软件培训

　　*/

　　int dp[21][21]; /* 存储LCS长度， 下标i,j表示序列X,Y长度 */

　　char X[21];

　　char Y[21];

　　int i, j;

　　void main（）

　　{

　　cin.getline（X,20）；

　　cin.getline（Y,20）；

　　int xlen = strlen（X）；

　　int ylen = strlen（Y）；

　　/* dp[0-xlen][0] & dp[0][0-ylen] 都已初始化0 */

　　for（i = 1; i <= xlen; ++i）

　　{

　　for（j = 1; j <= ylen; ++j）

　　{

　　if（X[i-1] == Y[j-1]）

　　{

　　dp[i][j] = dp[i-1][j-1] + 1;南京Java软件培训

　　}else if（dp[i][j-1] > dp[i-1][j]）

　　{

　　dp[i][j] = dp[i][j-1];

　　}else

　　{

　　dp[i][j] = dp[i-1][j];

　　}

　　}

　　}

　　printf（"len of LCS is: %d\n", dp[xlen][ylen]）；

　　/* 输出LCS 本来是逆序打印的，可以写一递归函数完成正序打印

　　这里采用的方法是将Y作为临时存储LCS的数组，最后输出Y

　　*/ 南京Java软件培训

　　i = xlen;

　　j = ylen;

　　int k = dp[i][j];

　　Y[k] = '\0';

　　while（i && j）

　　{

　　if（dp[i][j] == dp[i-1][j-1] + 1）

　　{

　　Y[--k] = X[i-1];

　　--i; --j;

　　}else if（dp[i-1][j] > dp[i][j-1]）

　　{

　　--i;

　　}else

　　{

　　--j;

　　}

　　}

　　printf（"%s\n",Y）；

　　}

　　江苏万和Java开发实训课程由5年以上软件项目开发经验的资深软件工程师、项目经理以及有着多年数据库管理经验的资深专家担纲授课，学员通过5个月的课程学习，可以掌握开发Java大型软件项目过程中所需要的软件技术、设计规范、开发流程、质量控制及项目管理，以及Oracle数据库相关知识内容。整个课程采用案例教学，授课与实践相结合，项目贯穿于各个阶段的课程当中，使学员能够学以致用。合格学员还可以获得由国际著名厂商Oracle公司所颁发的Oracle认证Java程序员（OCJP）、Oracle认证Web组件开发专家（OCWCD）、Oracle认证数据库管理员（OCA）等权威国际认证证书，合格学员保证100%就业。