LCS

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;
}