Longest Common Subsequence

// Longest Common Subsequence
/*
Input: 2 Strings: X and Y
*/

#include <iostream>
#include <string>
#include <iomanip>
#define TAB 3
#define SIZE 100
using namespace std;

char B[SIZE][SIZE];
int C[SIZE][SIZE];

void LCS_length(string X, string Y, int m, int n) {
    for (int i = 1; i <= m; i++)
        C[i][0] = 0;
    for (int i = 0; i <= n; i++)
        C[0][i] = 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] = 1 + C[i - 1][j - 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] = '<';
            }
        }
}


void print_LCS(string X, int i, int j) {
    if (i == 0 || j == 0)
        return;
    if (B[i][j] == '\\') {
        print_LCS(X, i - 1, j - 1);
        cout << X[i - 1];
    }
    else if (B[i][j] == '^')
        print_LCS(X, i - 1, j);
    else
        print_LCS(X, i, j - 1);
}


void match(string X, string Y, int m, int n) {
    string Xi = X, Yj = Y;
    for (int i = m, j = n; i > 0 && j > 0;) {

        if (B[i][j] == '\\') {
            Xi[i - 1] = '_';
            Yj[j - 1] = '_';
            i--;
            j--;
        }
        else if (B[i][j] == '^')
            i--;
        else
            j--;
    }

    cout << "   ";
    for (int i = 0; X[i]; i++) {
        if (Xi[i] == '_')
            cout << "_";
        else
            cout << " ";
    }
    cout << endl << "X: " << X << endl;
    cout << "   ";
    for (int i = 0; Y[i]; i++) {
        if (Yj[i] == '_')
            cout << "_";
        else
            cout << " ";
    }
    cout << endl << "Y: " << Y << endl << endl;
}


void print_Table(string X, string Y, int m, int n) {
    cout << "C Table: " << endl;
    cout << setw(TAB * 2) << "";
    for (int i = 0; i <= n; i++)
        cout << setw(TAB) << i;
    cout << endl;
    cout << setw(TAB * 3) << "";
    for (int i = 0; Y[i]; i++)
        cout << setw(TAB) << Y[i];
    cout << endl;
    for (int i = 0; i <= m; i++) {
        cout << setw(TAB) << i;
        if (i == 0)
            cout << setw(TAB) << "";
        else
            cout << setw(TAB) << X[i - 1];
        for (int j = 0; j <= n; j++)
            cout << setw(TAB) << C[i][j];
        cout << endl;
    }
    cout << endl;

    cout << "B Table: " << endl;
    cout << setw(TAB * 2) << "";
    for (int i = 1; i <= n; i++)
        cout << setw(TAB) << i;
    cout << endl;
    cout << setw(TAB * 2) << "";
    for (int i = 0; Y[i]; i++)
        cout << setw(TAB) << Y[i];
    cout << endl;
    for (int i = 1; i <= m; i++) {
        cout << setw(TAB) << i;
        if (i == 0)
            cout << setw(TAB) << "";
        else
            cout << setw(TAB) << X[i - 1];
        for (int j = 1; j <= n; j++)
            cout << setw(TAB) << B[i][j];
        cout << endl;
    }
    cout << endl;
}



int main() {
    string X, Y;
    cout << "String X: ";
    getline(cin, X);
    cout << "String Y: ";
    getline(cin, Y);
    int m, n;
    m = X.length();
    n = Y.length();

    LCS_length(X, Y, m, n);
    cout << "Length of Longest Common Subsequence: " << C[m][n] << endl;
    cout << "Longest Common Subsequence: ";
    print_LCS(X, m, n);
    cout << endl;
    match(X, Y, m, n);
    print_Table(X, Y, m, n);

    return 0;
}