最长公共子串(LCS)

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是 最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

// Eequal matrix:            arr matrix:
//   a b a b                   a b a b
// c 0 0 0 0                 c 0 0 0 0
// a E 0 1 0         ==>     a 1 0 1 0        ==>  aba
// b 0 E 0 1                 b 1 2 1 2
// a 1 0 E 0                 a 1 2 3 2

// 亲测，部分原创。
// 参考：//blog.csdn.net/wangwh485/article/details/6754764

#include "stdafx.h"
#include <string.h>
#include <stdlib.h>

#define MSTRLEN 100

char* maxCommStr(char *str_x, char *str_y, int *longest)
{
    int xlen = strlen(str_x);
    int ylen = strlen(str_y);
    int i,j,max,end;
    char *p_ret = NULL;
    int arr[MSTRLEN][MSTRLEN];

    if(NULL == str_x || NULL == str_y)
        return NULL;
    // initial
    max=end=0;
    for(i=0; i<MSTRLEN; ++i)
    {
        for(j=0; j<MSTRLEN; ++j)
        {
            arr[i][j] = 0;
        }
    }
    // find longest commen of the two string
    for(i=0; i<ylen; ++i)
    {
        for(j=0; j<xlen; ++j)
        {
            if(str_x[j] == str_y[i])
            {
                if(0 == j || 0 == i)
                    arr[i][j] = 1;
                else
                    arr[i][j] = arr[i-1][j-1] + 1;
            }
            if(arr[i][j] > max)
            {
                max = arr[i][j];
                end = j;
            }
        }
        for(j=0; j<xlen; ++j)
        {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    // deal with return value
    *longest = max;
    p_ret = (char *)malloc(max+1);
    for(i=0; i<max; i++)
    {
        p_ret[i] = str_x[end+1-max+i];
    }
    p_ret[i] = '\0';

    return p_ret;
}

// a better one
char* strLCS(char *str_x, char *str_y, int *longest)
{
    int xlen = strlen(str_x);
    int ylen = strlen(str_y);
    int i,j,max,end;
    char *p_ret = NULL;
    int tmp[MSTRLEN], arr[MSTRLEN];

    if(NULL == str_x || NULL == str_y)
        return NULL;
    // initial
    max=end=0;
    for(i=0; i<xlen; ++i)
    {
        tmp[i] = 0;
    }
    // find longest common of the two string
    for(i=0; i<ylen; ++i)
    {
        for(j=0; j<xlen; ++j)
        {
            if(str_x[j] == str_y[i])
            {
                if(0 == j)
                    arr[j] = 1;
                else
                    arr[j] = tmp[j-1] + 1;
            }
            if(arr[j] > max)
            {
                max = arr[j];
                end = j;
            }
        }
        for(j=0; j<xlen; ++j)
        {
            tmp[j] = arr[j];
            printf("%d ", arr[j]);
            arr[j] = 0;
        }
        printf("\n");
    }
    // deal with return value
    *longest = max;
    p_ret = (char *)malloc(max+1);
    for(i=0; i<max; i++)
    {
        p_ret[i] = str_x[end+1-max+i];
    }
    p_ret[i] = '\0';

    return p_ret;
}

int _tmain(int argc, _TCHAR* argv[])
{
    char * strA = "21232523311324";
    char * strB = "312123223445";
    // result should be: 21232, len=5
    int maxlen = 0;
    char *strLcs = maxCommStr(strA, strB, &maxlen);
    //char *strLcs = strLCS(strA, strB, &maxlen);

    printf("\nlongest is:%s, len=%d\n", strLcs, maxlen);

    free(strLcs);

    return 0;
}