动态规划法求解最长公共子序列(含Java代码).doc

《动态规划法求解最长公共子序列(含Java代码).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公共子序列问题徐康123183一．算法设计假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C[(m+1)*(n+1)]，记录Xi与Yj的LCS的长度。将C[i,j]分为三种情况：若i=0或j=0时，C[i,j]=0；若i,j>0且X[i]=Y[j]，C[i,j]=C[i-1,j-1]+1；若i,j>0且X[i]Y[j],C[i,j]=max{C[i-1,j],C[i,j-1]}。再使用一个m*n的二维数组b，b[i,j]记录C[i,j]的来向:若X[i]=Y[j]，则B[i,j]中记入“↖”，记此时b[i,j]=1；若X[

2、i]Y[j]且C[i-1,j]>C[i,j-1]，则b[i,j]中记入“↑”，记此时B[i,j]=2；若X[i]Y[j]且C[i-1,j]

3、return;Ifb[i,j]=1then/*X[i]=Y[j]*/{LCS_Output(b,X,i-1,j-1)；将X[i]保存至LCS[len-i]；}elseifb[i,j]=2then/*X[i]¹Y[j]且C[i-1,j]>C[i,j-1]*/LCS_Output(b,X,i-1,j)elseifb[i,j]=3then/*X[i]¹Y[j]且C[i-1,j]

4、ut(b,X,i-1,j)LCS_Output(b,X,i,j-1)}二．算法时间复杂度分析由上述对算法的分析得知，求辅助数组C和B所消耗的时间复杂度为O（mn），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。显然，最好的情况是m=n并且B中的所有值都为1（按斜对角线方向搜索），此时时间复杂度为O（n）。当X和Y序列不存在公共子序列时为算法的最坏情况，因为此时C数组的所有元素都为0，B在每一个节点都要沿着两个不同的方向搜索，即每次都要调用两次LCS_Output,当调用到i=0或j=0时返回，直到搜索完整个

5、m*n数组才结束。该时间复杂度就是计算从点（m,n）到i=0或j=0的所有路径。建立如上图的直角坐标系，设点S（m，n）,轴上的坐标点P1(1,0)到Pm(m,0)，轴上的系列坐标点Q1(0,1)到Qn(0,n)。因为是搜索路径的边界上的点，点不能直接到达点，点也不能直接到达，所以点到和的路径数等价于到点和点的路径数，又因为点到路径数为，设总路径数为，则有三．程序流程图如下所示二．程序源码packageHomework2;importjava.io.BufferedReader;importjava.io.IOException;importja

6、va.io.InputStreamReader;importjava.util.HashSet;importjava.util.Set;publicclassLCS{intC[][];intB[][];SetLCS_SET=newHashSet();//使用集合去重publicintLCSLength(charX[],charY[]){//返回公共子序列长度intm=X.length;intn=Y.length;C=newint[X.length][Y.length];B=newint[X.length][Y.length];for(inti=0

7、;iC[i][j-1]){C[i][j]=C[i-1][j];B[i][j]=2;}elseif(C[i-1][j]

8、se{C[i][j]=C[i-1][j];B[i][j]=4;}}}returnC[m-1][n-1];}publicvoidLCS_O