一 問題引入

在生物學中，經常需要比較兩個不同生物的DNA，一個DNA串由由一串稱為堿基的的分子組成，堿基有鳥嘌呤，腺嘌呤，胞嘧啶，胸腺嘧啶四中，我們用英文字母的首字母表示四種堿基，那么DNA就是在有限集{A,C,G,T}上的一個字符串。例如某種生物的DNA序列為：S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA，S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA，我們比較兩個DNA串的原因就是希望確定他們的相似度，作為衡量兩個物種相似度的標準。如果一個串是另外一個串的子串，那么它們就是相似的，但是這里彼此都不是彼此的子串。于是我們就有了新的衡量標準：尋找一個新串S3，使得S3中的元素都在S1，S2中出現過，且不要求連續，但是堿基在三個串中出現的順序一定要相同。可以找到的S3的長度越長，表明兩個物種越相似！

二?問題描述
給定兩個字符串X[A,B,C,B,D,A,B]和Y[B,D,C,A,B,A],求X和Y的最長公共子序列LCS

三 思路

1 采用暴力破解法: 掃描X所有的可能子串, 取其中一個字符時候,存在 取或不取兩種情況, 假設X字符串有M個字符,則子串個數為2的M次方,

假設Y有N個字符,將M中取出的子串與Y中進行對比,最后的時間復雜度為 N*2^M， ?簡直是龜速啊。。。

2 簡化方案

?2.1 從題目描述中?X = [A,B,C,B,D,A,B] ,?Y[B,D,C,A,B,A] ,目測最大公共子串為 BDAB , BCAB ,最長為4.

?2.2 假設從一開始就知道X,Y的最大長度為4 ，那么只要關心X為4的子串與Y進行對比,這樣效率就提高了.

?2.3 進一步假設X字符串轉為char數組后坐標為{0,1,2,3,4.....M} , 同理Y為{0,1,2,3...N}

? ?假設 ?i ?<= M , j <= N ?, c[i][j] =LCS( X,Y) ?. // i ,j 為一個int整數 ?, c[i][j]為 X的char數組{0,1,2,3....i} 和Y的char數組{0,1,2,3...j} 最大公共子串的長度

?// LCS 為?longestcommon?subsequence ( ?最長公共子串 ) 的縮寫 .

? ?那么對于X{0,1,2,3.....M} , Y{0,1,2,3....N}的最大公共子串長度為

? ?c[i][j] + LCS(X1,Y1)

?其中 X1 的坐標{ i+1,i+2,.....M } ,Y1坐標為{j+1,j+2....N}.

? 求最大公共子串長度總結 : ?一部分長度( 假設已知) ?+ 另外一部長度( 需要求的?)?

四 公式

最大公共子串公式1

? if (X[i] == Y[j] ) ??c[i][j] = c[i-1][j-1] + 1 ?

? ?證明 :

假設X , Y (見圖1) , 在X {0，1，2，...i} , Y {0,1,2,3...j} 中最長公共子串長度為 k ,那么 在X{0,1,2,3...,i-1} ,Y{0,1,2,3,...,j-1}(見圖2)中最長公共子串長度為k-1

圖1

圖2

反證法 : X{0,1,2,3...,i-1} ,Y{0,1,2,3,...,j-1}中最長公共子串長度為k-1不成立, 即存在一個w ( w > k-1 ) ,那么 如上圖2 , 當 X[i] == Y[j] 時候, 即在X {0，1，2，...i} , Y {0,1,2,3...j} 中, 最大公共子串長度為 w+1 > ( ?k-1 ) +1 > k ,這與原命題矛盾,所以不存在這樣一個w值.

即 ?? if (X[i] == Y[j] ) ??c[i][j] = c[i-1][j-1] + 1 ?

最大公共子串公式2

? if (X[i] != Y[j] ) ?c[i][j] = max( c[i][j-1] , c[i-1][j] ) ?// max (a ,b) 返回a,b兩個數中最大的一個 ,如果相等,則返回a

理解 : c[i][j] 對應圖3 , c[i-1][j] 對應圖4, c[i][j-1]對應圖5, 那么最大公共子串長度一定是c[i-1][j] 和c[i][j-1]中的一個 ,用上面反證法即可證明.

圖3

圖4

圖5

五 遞歸調用圖

假設X{0,1,2,3..M},Y{0,1,2,3,...N} 中M =7 , N = 6,那么它的調用圖如下.

從這幅圖中看出

1 樹的高度為 M+N = 7+6 = 15

2 時間復雜度 2^(M+N) = 2^13 (比暴力破解時間N*2^M=6*2^7還要多很多, 假設不采用備忘錄法和沒有重復情況下, 動態規劃時間復雜度比暴力破解復雜度高很多,但?經測試在M=29，N=28,時候 ,暴力破解法時間為 300萬次 ,動態規劃調用1000多次,后面有代碼,可自行測試)

3 有少量重復調用,比如紅框1和紅框2，都是遞歸6,5這種情況

六 動態規劃的特征

1 最優子結構 (包含問題最優解),如?最大公共子串公式2 .

2 重復子問題,如?五 遞歸調用圖

七 自頂向下+備忘錄法 java代碼

偽代碼 ?

LCS(x,y,i,j)if(x[i]==y[j]) c[i][j] = LCS(x,y,i-1,j-1)+1else c[i][j] = max(LCS(x,y,i-1,j) , LCS(x,y,i,j-1)) return c[i][j]
java代碼

LCS.java

public class LCS {private static int[][] c;private static int counter;/*** 判斷是否為空* */private static boolean isNullOrBlank(String source){if(source==null||"".equals(source.replace(" ", ""))) return true;return false;}/*** 得到最長公共子串* */public static int getLcs(String xStr,String yStr){if( isNullOrBlank(xStr) || isNullOrBlank(yStr) ) return 0;char[] xChar = xStr.toCharArray();char[] yChar = yStr.toCharArray();c = new int[xChar.length][yChar.length];int lcsMaxNumber = getLcsMaxNumber(xChar,yChar,xChar.length-1,yChar.length-1);return lcsMaxNumber;}private static int max(int x,int y){if(x>y) return x;return y;}// /** // * 不采用備忘錄法 // * 得到LCS最長公共子串的長度 // * */ // private static int getLcsMaxNumber(char[] x,char[] y,int i,int j){ // counter++; // if(i>=0&&j>=0){ // c[i][j]初始化為0，當不為0時,表示已經遍歷過 // if(x[i]==y[j]){ // c[i][j] = getLcsMaxNumber(x,y,i-1,j-1) + 1; // }else{ // c[i][j] = max(getLcsMaxNumber(x,y,i-1,j),getLcsMaxNumber(x,y,i,j-1)); // } // System.out.println("counter = "+counter+" c["+i+"]["+j+"] = " + c[i][j]); // return c[i][j]; // } // // return 0; // }/*** 備忘錄法* 得到LCS最長公共子串的長度* */private static int getLcsMaxNumber(char[] x,char[] y,int i,int j){counter++;if(i>=0&&j>=0){ if(c[i][j]==0){if(x[i]==y[j]){ // c[i][j]初始化為0，當不為0時,表示已經遍歷過c[i][j] = getLcsMaxNumber(x,y,i-1,j-1) + 1;}else{c[i][j] = max(getLcsMaxNumber(x,y,i-1,j),getLcsMaxNumber(x,y,i,j-1));} }System.out.println("counter = "+counter+" c["+i+"]["+j+"] = " + c[i][j]);return c[i][j];}return 0;}public static void main(String[] args) { // String x = "ABCBDAB"; // String y = "BDCABA";String x = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";String y = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";int number = LCS.getLcs(x, y);System.out.println(number);}} 對于前面提到的DNA的輸出最大公共子串長度為20

八 回溯法求最大公共子串

回溯法原理

假設?X = "ABCBDAB"; ?Y= "BDCABA",它們生成一副下面的圖

↖???↑???←符號解釋
?↖ 輸出該y{j}的值，并且向左斜角走一步 ? ↑ 表示向上走一步? ??←向左走一步
那么當 i = 7 , j = 6時候, 輸出元素為?ABCB ,把該字符串反向后,為BCBA( BCBA即為X和Y的最大公共子串?)
最大公共完整java代碼 （代碼中 b+c 為對應上面回溯原理中的圖） public class LCS2 {private static int[][] c; //保存長度private static char[][] b; //保存特殊符號 ↖ ↑ ←/*** 判斷是否為空* */private static boolean isNullOrBlank(String source){if(source==null||"".equals(source.replace(" ", ""))) return true;return false;}/*** 得到最長公共子串* */public static String getLCS(String x,String y){//判斷x,y是否為空if( isNullOrBlank(x) || isNullOrBlank(y) ) return null;//初始化變量int m = x.length();int n = y.length();b = new char[m][n];c = new int[m][n];char[] xChar = x.toCharArray();char[] yChar = y.toCharArray();//調用獲取最大公共子串長度方法getLcsMaxNumber(xChar,yChar,xChar.length-1,yChar.length-1);//回溯法得到最長公共子串StringBuffer sb = new StringBuffer();PRINT_LCS(sb,xChar,yChar,m-1,n-1);return sb.toString();}private static int max(int x,int y){if(x>y) return x;return y;}/*** 備忘錄法* 得到LCS最長公共子串的長度* */private static int getLcsMaxNumber(char[] x,char[] y,int i,int j){if(i>=0&&j>=0){ if(c[i][j]==0){if(x[i]==y[j]){ // c[i][j]初始化為0，當不為0時,表示已經遍歷過c[i][j] = getLcsMaxNumber(x,y,i-1,j-1) + 1;b[i][j] = '↖';}else{int i_1 = getLcsMaxNumber(x,y,i-1,j);int j_1 = getLcsMaxNumber(x,y,i,j-1);if(i_1>j_1){c[i][j] = i_1;b[i][j] = '↑';}else{c[i][j] = j_1;b[i][j] = '←';}} }return c[i][j];}return 0;}//回溯法得到最長公共子串private static void PRINT_LCS(StringBuffer sb,char[] x,char[] y,int i,int j){if(i==0 || j==0 ){if(b[i][j]=='↖'){sb.append(x[i]);}return ;}if(b[i][j]=='↖'){PRINT_LCS(sb,x,y,i-1,j-1);sb.append(x[i]);}else if(b[i][j]=='↑'){PRINT_LCS(sb,x,y,i-1,j);}else if(b[i][j]=='←'){PRINT_LCS(sb,x,y,i,j-1);}}public static void main(String[] args) { // String x = "ABCBDAB"; // String y = "BDCABA";String x = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";String y = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";String lcs = LCS2.getLCS(x, y);System.out.println("最大公共子串為 = " + lcs);}} 問題引入中?DNA序列為：S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA，S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA的, 由該程序求得,最大公共子串為 ?= GTCGTCGGAAGCCGGCCGAA

總結

以上是生活随笔為你收集整理的动态规划之最长公共子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。