算法导论之动态规划：最长公共子序列

朴灿烈づ我的快乐病毒、 2022-07-24 06:18 148阅读 0赞

**公共子序列**定义：

给定一个序列X=<x1,x2,x3……,xm>,另一个序列Z=<z1,z2,z3……,zk>满足如下条件时称为X的子序列。

即存在一个严格递增的X的下标序列<i1,i2,……ik>，对所有的j=1,2,……,k，满足xi=zj。

**动态规划算法的4个步骤**：

1.刻画一个最优解的结构特征。

2.递归地定义最优解的值。

3.计算最优解的值，通常采用自底向上的方法。

4.利用计算出的信息构造一个最优解。

第一步、我们刻画出最长公共子序列的特征：

令X=<x1,x2……,xm>和Y=<y1,y2……,yn>为两个序列，Z=<z1,z2……，zk>为X和Y的任意LCS。

1.如果x\[m\]=y\[n\]，则z\[k\]=x\[m\]=y\[n\]，且Z\[k-1\]是X\[m-1\]和Y\[n-1\]的一个LCS。

2.如果x\[m\]!=y\[n\]，则z\[k\]!=x\[m\]，且意味着Z是X\[m-1\]和Y的一个LCS。

2.如果x\[m\]!=y\[n\]，则z\[k\]!=y\[n\]，且意味着Z是X和Y的\[n-1\]一个LCS。

第二步、一个地归解：

c\[i,j\]=0                                          若i=0或j=0

c\[i,j\]=c\[i-1\]\[j-1\]+1                        若i,j>0且x\[i\]=y\[j\]

c\[i,j\]=max(c\[i\]\[j-1\],c\[i-1\]\[j\])         若i,j>0且x\[i\]!=y\[j\]

第三步、计算LCS的长度

时间复杂度为O(mn)。

第四步、构造LCS。

时间复杂度为O(m+n)。

代码实现如下：

#include <stdio.h>
    #include<String.h>
    
    int LCS_LENGTH(char *Xstring,char *Ystring,int Xlen,int Ylen,int c[][Ylen+1],char b[][Ylen+1]){
    	int i=1;
    	for(;i<Xlen+1;i++){
    		c[i][0]=0;
    	}
    	int j=0;
    	for(;j<Ylen+1;j++){
    		c[0][j]=0;
    	}
    	for(i=1;i<Xlen+1;i++){
    		for(j=1;j<Ylen+1;j++){
    			if(Xstring[i-1]==Ystring[j-1]){
    				c[i][j]=c[i-1][j-1]+1;
    				b[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[Xlen][Ylen];
    }
    void PRINT_LCS(int Ylen,char b[][Ylen+1],char *Xstring,int i,int j){
    	if(i==0 || j==0){
    		return;
    	}
    	if(b[i][j]=='='){
    		PRINT_LCS(Ylen,b,Xstring,i-1,j-1);
    		printf("%c",Xstring[i-1]);
    	}else if(b[i][j]=='|'){
    		PRINT_LCS(Ylen,b,Xstring,i-1,j);
    	}else if(b[i][j]=='-'){
    		PRINT_LCS(Ylen,b,Xstring,i,j-1);
    	}
    }
    int main(int argc, char *argv[])
    {
    	char Xstring[] = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
    	char Ystring[] = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
    	int Xlen=strlen(Xstring);
    	int Ylen = strlen(Ystring);
    	int c[Xlen+1][Ylen+1];
    	char b[Xlen+1][Ylen+1];
    	int len = LCS_LENGTH(Xstring,Ystring,Xlen,Ylen,c,b);
    	printf("the common String's length is:%d\nXstring len is:%d\nYstrring len is:%d\n\n",len,Xlen,Ylen);
    	char rs[len];
    	int flag=len;
    	int i=Xlen,j=Ylen;
    	int count=0;
    	while(i>0&&j>0){
    			printf("this is b[%d][%d],\tcount is %d,\tXstring[%d] is %c,\tYstring[%d] is%c\n",i,j,++count,i-1,Xstring[i-1],j-1,Ystring[j-1]);
    			if(b[i][j]=='='){
    				rs[--flag]=Xstring[--i];
    				printf("%d,%d,%c\n",i+1,j,rs[flag]);
    				j--;
    			}else if(b[i][j]=='|'){
    				printf("%c\n",'|');
    				i--;
    			}else if(b[i][j]=='-'){
    				printf("%c\n",'-');
    				j--;
    			}
    	}
    	int w= 0;
    	for(;w<len;w++){
    		printf("%c",rs[w]);
    	}
    	printf("\n");
    	PRINT_LCS(Ylen,b,Xstring,Xlen,Ylen);
    	return 0;
    }

上面第四步的构造LCS，使用了两种方式，任选其一即可。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51419556  
作者：WSYW126

最长公共连续子串

package cc.wsyw126.java.nowcoder;
    
    import java.util.Scanner;
    
    /** * Created by Administrator on 2017/4/12. */ public class LCSContinuous {
        public int LCS_LENGTH(String a, String b) throws Exception {
            int result = 0;
            if (a == null || b == null) {
                throw new Exception("null Exception!");
            }
            if (a.length() == 0 | b.length() == 0) {
                return result;
            }
            int raw = a.length(), column = b.length();
            int[][] mark = new int[raw+1][column+1];
            for (int i = 0; i <= raw; i++) {
                mark[i][0] = 0;
            }
            for (int i = 0; i <= column; i++) {
                mark[0][i] = 0;
            }
            for (int i = 0; i < raw; i++) {
                for (int j = 0; j < column; j++) {
                    if (a.charAt(i) == b.charAt(j)) {
                        if (i-1<0 || j-1 <0 || a.charAt(i-1) == b.charAt(j-1)) {
                            mark[i+1][j+1] = mark[i][j]+1;
                        } else {
                            mark[i+1][j+1] = 1;
                        }
                    }else {
                        if (mark[i][j+1] >= mark[i+1][j]) {
                            mark[i+1][j+1] = mark[i][j+1];
                        }else {
                            mark[i+1][j+1] = mark[i+1][j];
                        }
                    }
                }
            }
            result = mark[raw][column];
            return result;
        }
    
        public static void main(String[] args) throws Exception {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()) {
                String a = scanner.nextLine();
                String b = scanner.nextLine();
                LCSContinuous lcs = new LCSContinuous();
                int i = lcs.LCS_LENGTH(a, b);
                System.out.println("i = " + i);
    
            }
        }
    }