LCS_LENGTH

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

vector<vector<char>> B(8, 7);

void LCS_LENGTH(const vector<char> &X, const vector<char> &Y);
void PRINT_LCS(const vector<vector<char>> &b, const vector<char> &X, int i, int j);

int main(string args[])
{
    vector<char> X(7);
    X[0] = 'A';
    X[1] = 'B';
    X[2] = 'C';
    X[3] = 'B';
    X[4] = 'D';
    X[5] = 'A';
    X[6] = 'B';

    vector<char> Y(6);
    Y[0] = 'B';
    Y[1] = 'D';
    Y[2] = 'C';
    Y[3] = 'A';
    Y[4] = 'B';
    Y[5] = 'A';

    LCS_LENGTH(X, Y);

    PRINT_LCS(B, X, 6, 6);
    cout << endl;

    system("PAUSE");
    return (0);
}

void LCS_LENGTH(const vector<char> &X, const vector<char> &Y)
{
    int m = X.size(); cout << "X.size() = " << X.size() << endl;
    int n = Y.size(); cout << "Y.size() = " << Y.size() << endl << endl;

    vector<vector<int>> c(m+1, n+1); cout << "c(" << c.size() << ", " << c[0].size() << ")" << endl;
    vector<vector<char>> b(m+1, n+1); cout << "b(" << b.size() << ", " << b[0].size() << ")" << endl << endl;

    for (int i = 0; i <= m; i++) c[i][0] = 0;
    for (int j = 1; j <= n; j++) c[0][j] = 0;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (X[i-1] == Y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = '\\';
            }
            else
            {
                if (c[i-1][j] >= c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    b[i][j] = '^';
                }
                else
                {
                    c[i][j] = c[i][j-1];
                    b[i][j] = '<';
                }
            }
            cout << " " << c[i][j] << " ";
            cout << b[i][j] << "\t";
        }
        cout << endl;
    }
    cout << endl;

    B = b;
}

void PRINT_LCS(const vector<vector<char>> &b, const vector<char> &X, int i, int j)
{
    if (i == 0 || j == 0) return;
    if (b[i][j] == '\\')
    {
        PRINT_LCS(b, X, i-1, j-1);
        //print X[i-1];
        cout << X[i-1] << " ";
    }
    else
    {
        if (b[i][j] == '^') PRINT_LCS(b, X, i-1, j);
        else PRINT_LCS(b, X, i, j-1);
    }
}