0001 #include <algorithm>
0002 using namespace std;
0003 
0004 unsigned int lcsIteration(char const * A, int n, char const * B, int m) {
0005    if (n < m) { swap(A, B); swap(n, m); } //make sure m <= n
0006    unsigned int* lcs1 = new unsigned int[m+1]; //the current two rows are
0007    unsigned int* lcs2 = new unsigned int[m+1]; //buffered alternatively
0008    memset(lcs1, 0x00, sizeof(unsigned int) * (m+1)); lcs2[0] = 0; //sentinels
0009    for (int i = 0; i < n; swap(lcs1, lcs2), i++)
0010       for (int j = 0; j < m; j++)
0011          lcs2[j + 1] = (A[i] == B[j]) ? 1 + lcs1[j] : max(lcs2[j], lcs1[j+1]);
0012    unsigned int solu = lcs1[m];
0013    delete[] lcs1;
0014    delete[] lcs2;
0015    return solu;
0016 }