首页 > 代码库 > 【动态规划】 之最长公共子序列LCS

【动态规划】 之最长公共子序列LCS

int lcs_len(char *a, char *b, int c[][N]){    int aLen=strlen(a),        bLen=strlen(b),        i,j;    for(i=0; i<=aLen; i++)        c[i][0]=0;    for(j=1; j<=bLen; j++)        c[0][j]=0;    for(i=1;i<=aLen;i++)        for(j=1;j<=bLen;j++)            if(a[i-1]==b[j-1])                c[i][j]=c[i-1][j-1]+1;            else                 c[i][j]=MAX( c[i-1][j],c[i][j-1] );    return c[i][j]; //返回的是长度}char *build_LCS(char *s,char *a, char *b){  //重建公共子序列    int k,i=strlen(a),        j=strlen(b), c[N][N];    k=lcs_len(a,b,c);    //s[k]=‘\0‘;    while(k>0)        if(c[i][j]==c[i-1][j])            i--;        else if(c[i][j]==c[i][j-1])            j--;        else{            s[--k]=a[i-1];            i--;            j--;        }        return s;}

 

【动态规划】 之最长公共子序列LCS