LCS -- 最长公共子序列

 问题描述

我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在严格上

升的序列< i1, i2, ..., ik >，使得对 j = 1, 2, ... ,k,  有 xij = zj。比如Z = < a, b, f, c >  是 X = < a, b,

c, f, b, c >的子序列。 

现在给出两个序列 X和 Y，你的任务是找到 X和 Y的最大公共子序列，也就是说要找

到一个最长的序列 Z，使得 Z 既是X的子序列也是 Y的子序列。

解题思路

很容易分析出递推关系：(s1,s2为两个字符串，i,j分别为他们的串字符下标）用 s1i 表示 s1 的前 i

个字符所构成的子串， s2j表示 s2 的前 j 个字符构成的子串，MaxLen(i, j)表示 s1i  和 s2j的最长公共子序列的长度

if( i ==0 || j == 0 ) {

MaxLen(i, j) = 0 //两个空串的最长公共子序列长度当然是 0 

}

else if( s1[i] == s2[j] ) 

MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;

else {

MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j));

}

非递归解法：（动态规划）

#define MAXSIZE 20
#define max(a,b) (a)>(b)?(a):(b)
int dp_lcs(){
    char str1[MAXSIZE];
    char str2[MAXSIZE];
    //maxlen[i][j] means max lcs of str[1..i] and str[1..j]
    int maxlen[MAXSIZE][MAXSIZE];
    printf("input two strings:\n");
    //initualize two strings, and str[0] in not for using.
    scanf("%s",str1+1);
    scanf("%s",str2+1);
    int len1=strlen(str1+1);
    int len2=strlen(str2+1);
    int i,j;
    for(i=0;i<=len1;i++){
        maxlen[i][0]=0;
    }
    for(j=0;j<=len2;j++){
        maxlen[0][j]=0;
    }
    //dp to run lcs
    for(i=1;i<=len1;i++){
        for(j=1;j<=len2;j++){
            if(str1[i]==str2[j]){
                maxlen[i][j]=maxlen[i-1][j-1]+1;
            }else{
                maxlen[i][j]=max(maxlen[i-1][j],maxlen[i][j-1]);
            }
      }
    }//end main_For
    return maxlen[len1][len2];
}
           

递归解法： 

#include<stdio.h>

int lcs(char *str1,char *str2){
    if(*str1=='\0'||*str2=='\0')return 0;
    if(*str1==*str2){
        return lcs(str1+1,str2+1)+1;
    }else{
        if(lcs(str1+1,str2)>lcs(str1,str2+1)){
            return lcs(str1+1,str2);
        }else{
            return lcs(str1,str2+1);
        }
    }
}

int main(){
    char a[10];
    char b[10];
    gets(a);
    gets(b);
    int len = lcs(a,b);
    printf("%d\n",len);
    return 0;
}