（学习9）最长子序列LCS算法

问题描述：给定两个序列X,Y，求这两个序列的最长公共子序列；

主要思想:动态规划

解析：

子序列：即序列中，下标按照严格递减所形成的序列即为子序列，

比如 X <A,B,C,B,A>,那么 ACB也是该序列的子序列

子序列可以有很多，但是最长子序列的长度是应该唯一的。

推论：

1：如果X_i=Y_j,那么Z_k=X_i=Y_j,则Z_k-1=X_i-1+Y_j-1

2：如果X_i !=Y_j,且Z_k != X_i,则Zk是X_i-1与Y_j的最长公共子序列

3：如果X_i !=Y_j,且Z_k !=Y_j,则Zk是X_i与Y_j-1的最长公共子序列

设：

X=<A,C,B,A,C> n=5

Y=<C,B,C,A> m=4

求这两个序列的最长子序列

C[i][j] 1<=i<=n 1<=j<=m

B[i][j] {删除x：0；删除y：1；删除x与y：2}，记录状态

伪代码设计:

算法一：给出算法的最长子序列的长度

for i->n:
     for j->m:
       if X[i]==Y[j]:
           C[i][j]=C[x-1][y-1]+1;
       else:
           C[i][j]=max{C[x-1][j],C[x][j-1]};

View Code

算法二：输出最长公共子序列

 f(B,i,j)
if i==0||j==0:
    return ;
if B[i][j]==2:
    Res[++len]=X[i];
//直接输出就是逆序了，所以我先存起来，最后逆序输出
    f(B,i-1,j-1);//删除两个
else if B[i][j]==0:
    f(B,i-1,j);//删除x
else:
    f(B,i,j-1);//删除y

View Code

代码实现

//
//  main.c
//  作业9
//
//  Created by yizhihenpidehou on 2020/4/21.
//  Copyright © 2020 yizhihenpidehou. All rights reserved.
//

#include <stdio.h>
#include <string.h>
const int maxen=30;
char X[maxen]={'0','A','C','B','A','C'};
char Y[maxen]={'0','C','B','C','A'};
//char X[maxen]={'0','A','B','C','D'};
//char Y[maxen]={'0','B','A','C'};
int C[maxen][maxen];
int B[maxen][maxen];
int len=0;//子序列长度
int res[maxen];//存放最长子序列
void LCS(int n,int m){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(X[i]==Y[j]){
                C[i][j]=C[i-1][j-1]+1;
                B[i][j]=2;//删除两个
            }
            else{
                if(C[i-1][j]>C[i][j-1]){
                    B[i][j]=0;//删除X
                    C[i][j]=C[i-1][j];
                }
                else{
                    B[i][j]=1;//删除Y
                    C[i][j]=C[i][j-1];
               //     printf("<= %d %d:%d
",i,j,B[i][j]);
                }
            
            }
        }
    }
}
void f(int i,int j){//输出最长公共序列
    if(i==0||j==0) return ;
    if(B[i][j]==2){
       // printf("%c ",X[i]);
        res[++len]=X[i];
        f(i-1,j-1);//删除两个
    }
    else if(B[i][j]==0){
        f(i-1,j);//删除X
    }
    else{
        f(i,j-1);//删除Y
    }
}
int main(int argc, const char * argv[]) {
    int n=5,m=4;
    memset(C, 0, sizeof(C));
    memset(B, -1, sizeof(B));
    LCS(n,m);
    f(n,m);
 /*   printf("
");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",C[i][j]);
        }
        printf("
");
    }
    printf("
");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",B[i][j]);
        }
        printf("
");
    }*/
    for(int i=len;i>0;i--){
        printf("%c",res[i]);
    }
    printf("
");
    return 0;
}

View Code