LCS (OP)

#include <iostream>
#include <vector>
#define izqui 1
#define arrib 2
#define diago 3

using namespace std;

string LCS (string &a, string &b)
{
    vector< vector<int> > m, p;

    int ta = a.size();
    int tb = b.size();

    m = vector< vector<int> > (ta+1, vector<int> (tb+1, 0) );
    p = vector< vector<int> > (ta+1, vector<int> (tb+1) );

    for (int i=1; i<=ta; i++)
    {
        for (int j=1; j<=tb; j++)
        {
            if ( a[i-1] == b[j-1] )
            {
                m[i][j] = m[i-1][j-1] + 1;
                p[i][j] = diago;
            }
            else
            {
                if (m[i-1][j] > m[i][j-1])
                {
                    m[i][j] = m[i-1][j];
                    p[i][j] = arrib;
                }
                else
                {
                    m[i][j] = m[i][j-1];
                    p[i][j] = izqui;
                }
            }
        }
    }

    string lcs;
    int i=ta, j=tb;
    while( m[i][j] )
    {
        if (p[i][j]==diago)
        {
            lcs = a[i-1] + lcs;
            i--, j--;
        }
        else if ( p[i][j] == arrib )
            i--;
        else if ( p[i][j] == izqui )
            j--;
    }

    return lcs;
}

int main()
{
    string a, b;

    cin>>a>>b;
    cout<<LCS(a,b);

    return 0;
}