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

1、算法设计公共子序列问 题徐康123183假设有两个序列X和Y,假设X和Y分别有m和n个元素，则建立一个 C(m+l)*(n+l), 二维数组记录X】与的LCS的长度。将Ci, J分为三种情况：若 i =0 或 j =0 时，Ci, j=0 ；若 i, j0 且 Xi=Yj,若 i, j0 且 Xi Yj, Ci, j=maxci-l, j, Ci, j-1。再使用一个m*n的二维数组b, bi, j记录Ci, j的来向：若 Xi=Yj, 若 XiYj则Bi, J中记入，记此时bi, J Ci-1, j=1 ；収W, j中记入“ f，”记此时Bi, j = 2 ；Ci, j-1*/else if

2、 bi, j=3 then /*XiYj且 Ci-1, jCi, j-1*/LCS_0utput(b, X, iYj且 Ci-else if bi, j=41, J=Ci, j-1*/LCS_Output(b, X, il, j)LCS Output (b, X, i, jl)算法时间复杂度分析由上述对算法的分析得知，求辅助数组C和B所消耗的时间复杂度为0( mn),而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。显然，最好的情况是m=n并且B中的所有值都为1(按斜对角线方向搜索)，此时时间复杂度为0( n)。当X和Y序列不存在公共子序列时为算法的最坏情况

3、，因为此时C数组的所有元素都为0, B在每一个节 点都要沿着两个不同的方向搜索，即每次都要调用两次LCS_0utput,当调用到i=0或j=0时返回， 直到搜索完整个m*n数组才结束。该时间复杂度就是计算从点(m,n)到1=0或j=0的所有路径。建立如上图的直角坐标系，设 点S ( m,n), x轴上的坐标点Pi(l, 0)到Pm(m, 0), y轴上的系列坐标点Qi(0, 1)到Qn(0,n)。因为Pi和Q j是搜索路径的边界上的点，点Pi 1不能直接到达点Pi,点Qji也不能直接到达 Qj ,所以点S (m, n)到Pi, P2,. . ., Pi,. . . , Pm和Qi , Q2 ,

4、，Q j ,，Qn的路径数等价 于 S(m, n)到点 Pi (1, 1), P2(2, 1), Pi.，(i. , 1,), Pm(.m, , 1)和点Q/ (1, 1), Q2 (1,2),., Q, (1, j),Qn，(1, n)的路径数，又因为点(m, n)到(i, j)路径数为 Cmn i J ,设总路径数为t,则有nm t Cmn 11 n iCnT m ji 1 J 1CnR J 3 Cx* CnU 1 CnV 2Cnx 3 C； Cninlmlnlncnmlcnml cn m 1 cn m 1nm cn m cn m二程序流程图如下所示Y得到LCS通过Set去重四.程序源码p

5、ackage Homework2;import java. io. BufferedReader:import java. io. IOException;import java. io. InputStreamReddei;import java. uti1. HashSet;import java .util. Set:public class LCS int C;int B；/使用集合去重/返回公共子序列Set LCS_SET = new HashSet();public int LCSLength(char X, charY) int m = X. 1 ength;int n 二 Yl

6、ength;C = newintXlengthY. length;B = new intX. lengthY. length; for (int i 二 0; i m; i+) Ci0二 0;Bi0 = 0;)for (int j = 0; j n; j+) COj = 0;BOj = 0;for (int i=l; i Cij - 1) Cij = Ci - lj; Bij = 2; elseif (Ci - lj Cij - 1) Cij = Cij - 11;Bij二 3; else Cij = Ci - lj：Bij二 4;return Cm - 1 n - 1;public void

7、 LCS_Output(int Direction, char X,int i, int j, int len, char LCS) int lcslen = len;if (i = 0| j 二二 0) LCS_SET. add(String valueOf(LCS); return;)if (Bij二二 1) LCSElen - 1二 Xi;len;LCS_Output(B,x,i - 1,J -1,len, LCS); elseif(Bij = 2) LCS_Output(B,X,i - 1,j,len,LCS); elseif (Bij二二3) LCS_Output(B,X, 1, J

8、 -1,len,LCS); elseif (Bij二二4) LCS_Output(B,X,i - 1,j,len,LCS);LCS_Output(B,X, 1, J -1,len,LCS);* param argspublic staticvoid main(String args) throws IOException / TODO Auto-generated method stubchar X, Y;BufferedReader buf = null;buf = new BufferedReader(new InputStreamReader(Systemin)；System, out.

9、 printin(请输入个序列“)；X = buf. readLine () toCharArray ();char X_temp = new char X length + 1:for (int i 二 0; i X length; i+) X_temp0二；X_tempi + 1二 Xi;System, out. println( 请输入个序列“);Y = buf. readLine (). toCharArray ();char Y_temp = new charY.1 ength + 1 ; for (int i = 0; i Y. 1 ength; i+) Y_temp0二；Y_te

10、mpi + 1 = Yi;)System .out. print (，X=，/ ); for (char x : X) System, out print(x);1System out println();System .out. print (Y二 );for (char y : Y) System out print(y);)System out. println ();LCS les = new LCS ();int len = les LCSLength(X_tenip, Y_temp);char LCS = new charlen;int m = X.length;int n 二 Ylength;System, out. println(最长公共子序列长度为:+ len) ; /输岀最长子序列长 度System, out. print (z/最长公共