最长公共子序列问题（LCS）给定两个序列\(X=<{x_1,x_2,...x_m}>和Y=<y_1,y_2,...y_n>\),求X和Y长度最长的公共子序列。总共分三个步骤：

步骤一：刻画最长公共子序列的特征

步骤二：一个递归解

步骤三：计算LCS的长度

上述过程我们有如下图来表示：

步骤4 构造LCS

这里我们用C++来构造这个算法：

//
//  main.cpp
//
//  Created by LZH on 2017/10/30.
//  Copyright © 2017年 梁中豪. All rights reserved.
//


#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

//计算LCS的长度
void LCS_LENGTH(char *X ,char *Y ,int **b ,int **c ,int &m ,int &n)
{
    //    int m = sizeof(X)/sizeof(char);
    //    int n = sizeof(Y)/sizeof(char);
    
    //    int b[m][n];
    //    int c[m][n];
    
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            if (X[i]==Y[j]) {
                c[i][j] = c[i-1][j-1]+1;
                b[i][j] = 1;
            }
            else if (c[i-1][j]>=c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
    }
}

void PRINT_LCS(int **b,char *X,int i,int j)
{
    if (i==0 || j==0) {
        return;
    }
    if (b[i][j]==1) {
        PRINT_LCS(b, X, i-1, j-1);
        cout << X[i] <<endl;
    }
    else if (b[i][j]==2)
    {
        PRINT_LCS(b, X, i-1, j);
    }
    else
    {
        PRINT_LCS(b, X, i, j-1);
    }
}

int main()
{
    char X[8] = {'x','A','B','C','B','D','A','B'};
    char Y[7] = {'y','B','D','C','A','B','A'};
    int m = sizeof(X)/sizeof(char);
    int n = sizeof(Y)/sizeof(char);
    int **b =new int*[m];
    for (int i = 0; i<m; i++) {
        b[i] = new int[n];
    }
    
    int **c = new int*[m];
    for (int i = 0; i<m; i++) {
        c[i] = new int[n];
    }
    LCS_LENGTH(X,Y,b,c,m,n);
    PRINT_LCS(b,X,m-1,n-1);
    return 0;
}