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 }