http://blog.csdn.net/v_JULY_v/article/details/6110269
我的算法，本质上和上篇博客中提到的算法是一样的：
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <stdint.h>
#include <string.h>
#include <pthread.h>
#include <vector>
#include <map>
#include <set>
using namespace std;
int LCS(const char* X, const char* Y, char* R) {
if (NULL == X || NULL == Y || NULL == R) {
return 0;
}
int xlen = strlen(X);
int ylen = strlen(Y);
map<int, map<int, int> > D;
for (int i = 0; i < xlen; ++i) {
int max = 0;
for (int j = 0; j < ylen; ++j) {
max = std::max(X[i] == Y[j] ? 1 : 0, max);
if (i > 0) {
max = std::max(D[i - 1][j], max);
if (j > 0) {
max = std::max(D[i - 1][j - 1] + (X[i] == Y[j] ? 1 : 0), max);
}
}
D[i][j] = max;
printf("(%d,%d) = %d\n", i, j, max);
}
}
return D[xlen - 1][ylen - 1];
}
int main(int argc, char* argv[]) {
const char* X = argc > 1 ? argv[1] : "abacbda";
const char* Y = argc > 2 ? argv[2] : "cbada";
char R[1024];
printf("X:%s\n", X);
printf("Y:%s\n", Y);
int ret = LCS(X, Y, R);
printf("ret:%d\n", ret);
return 0;
}