LCS

#include <iostream>
#include <vector>
#include <queue>

#define ARRIBA 1
#define IZQUIERDA 2
#define DIAGONAL 3

using namespace std;

string CLS (string &a, string &b)
{
    int tamA = a.size();
    int tamB = b.size();

    vector < vector<int> > m (tamA+1, (vector<int> (tamB+1, 0) ) );
    vector < vector<int> > p (tamA+1, (vector<int> (tamB+1, 0) ) );

    for (int i=1; i<=tamA; i++)
    {
        for (int j=1; j<=tamB; j++)
        {
            if ( a[i-1] == b[j-1] )
            {
                m[i][j] = m[i-1][j-1] + 1;
                p[i][j] = DIAGONAL;
            }
            else if (m[i][j-1] >= m[i-1][j])
            {
                m[i][j] = m[i][j-1];
                p[i][j] = IZQUIERDA;
            }
            else
            {
                m[i][j] = m[i-1][j];
                p[i][j] = ARRIBA;
            }
        }
    }

    string resultado;

    int i=tamA, j=tamB;
    while ( m[i][j] )
    {
        if (p[i][j] == ARRIBA)
            i--;
        else if (p[i][j] == IZQUIERDA)
            j--;
        else if (p[i][j] == DIAGONAL)
        {
            resultado = a[i-1] + resultado;
            i--, j--;
        }
    }

    return resultado;
}

int main()
{
    string a = "ancle";
    string b = "pale";

    string lcs = CLS(a,b);

    cout<<lcs;

    return 0;
}