0001 #include <algorithm>
0002 using namespace std;
0003 
0004 unsigned int lcsM(char const * A, int n, char const * B, int m, unsigned int * const lcs, int const M) {
0005    if (n < 1 || m < 1)
0006       return 0;
0007    if (UINT_MAX != lcs[(n-1)*M + m-1])
0008       return lcs[(n-1)*M + m-1]; //recursion stops here
0009    return lcs[(n-1)*M + m-1] = (A[n-1] == B[m-1]) ?
0010             1 + lcsM(A, n-1, B, m-1, lcs, M) :
0011             max( lcsM(A, n-1, B, m, lcs, M), lcsM(A, n, B, m-1, lcs, M) );
0012 }
0013 
0014 unsigned int lcsMemoization(char const* A, int n, char const* B, int m) {
0015    unsigned int * lcs = new unsigned int[n*m]; //a lookup-table of all sub-solutions
0016    memset(lcs, 0xFF, sizeof(unsigned int)*n*m); //initialized with n*m UINT_MAX's
0017    unsigned int solu = lcsM(A, n, B, m, lcs, m);
0018    delete[] lcs;
0019    return solu;
0020 }