最长公共子序列问题[LCS]

题目：字符串A："ABCBDAB"， 字符串B："BDCABA"，求一个A和B的LCS的解
思路：算法导论上对这题有个完整的解释，依照算法导论上的DP方程，我们很容易能得到如下的代码

2017-3-23 代码更新如下：

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

string LCS(const string & strA, const string & strB) {
    vector<vector<int> > matrix(strA.size()+1, vector<int>(strB.size()+1, 0));

    for (int i=0; i<strA.size(); ++i) {
        for (int j=0; j<strB.size(); ++j) {
            if (strA[i] == strB[j]) {
                matrix[i+1][j+1] = matrix[i][j] + 1;
            } else {
                matrix[i+1][j+1] = std::max(matrix[i][j+1], matrix[i+1][j]);
            }
        }
    }

    int i = strA.size();
    int j = strB.size();
    int n = matrix[i][j];
    string strC;
    strC.resize(n);
    while (n) {
        while (matrix[i-1][j] == n) {
            --i;
        }
        while (matrix[i][j-1] == n) {
            --j;
        }
        strC[n-1] = strA[i-1];
        --n;
        --i;
        --j;
    }

    return strC;
}

int main(int argc, char ** argv)
{
    string strA = "ABEDEBGH";
    string strB = "BEFH";

    string strC = LCS(strA, strB);

    puts(strC.c_str());

    return 0;
}

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

void Output(const vector<vector<int> > & matrix)
{
    for(int i=0; i<matrix.size(); ++i) {
        for (int j=0; j<matrix[i].size(); ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

void AllocMatrix(vector<vector<int> > & matrix, int n, int m)
{
    matrix.clear();
    matrix.assign(n, vector<int>(m, 0));
}

void LCS_Matrix(const string & strA, const string & strB, vector<vector<int> > & matrix, int & N, int & M) 
{
    N = strA.size() + 1;
    M = strB.size() + 1;
    
    AllocMatrix(matrix, N, M);

    for (int i=1; i<N; ++i) {
        for (int j=1; j<M; ++j) {
            if (strA[i-1] == strB[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
            } else {
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1]); 
            }
        }
    }
}

string LCS(const string & strA, const string & strB)
{
    vector<vector<int> > matrix;
    int N = 0;
    int M = 0;

    LCS_Matrix(strA, strB, matrix, N, M);

    string strLCS; 
    strLCS.resize(matrix[N-1][M-1]);
    int k = strLCS.size() - 1;
    int i = N-1;
    int j = M-1;
    while (k >= 0) {
        if (matrix[i-1][j] == matrix[i][j]) {
            --i;
            continue;
        }
        else if (matrix[i][j-1] == matrix[i][j]) {
            --j;
            continue;
        }
        else { 
            strLCS[k--] =  strA[i-1];
            --i, --j;
        }
    }

    return strLCS;
}

int main(int argc, char ** argv)
{
    string strA = "ABCBDAB";
    string strB = "BDCABA";

    string strLCS = LCS(strA, strB);

    cout << "A:" << strA << endl;
    cout << "B:" << strB << endl;
    cout << "LCS:" << strLCS << endl;

    return 0;
}

代码使用C++编写的，重要的部分都是手写的，但是不重要的部分都是采用STL库中容器和算法来实现的。
LCS_Matrix的函数实现的就是DP方程的内容。