LCS记录

　　如题：求两个序列的最长公共序列。(如：“ABCBDAB”与“BCDB”最长公共序列为"BCDB")代码如下：

#define MAX_SIZE 200
char a[MAX_SIZE], b[MAX_SIZE], str[MAX_SIZE];
int num[MAX_SIZE][MAX_SIZE];
//计算最优值，即最长公用字符串的长度
int lcs_len(int a_length, int b_length)
{
    int t, s;
    if (a_length == 0 || b_length == 0)
        num[a_length][b_length] = 0;
    else if (a[a_length - 1] == b[b_length - 1])
        num[a_length][b_length] = lcs_len(a_length - 1, b_length - 1) + 1;
    else
    {
        t = lcs_len(a_length, b_length - 1);
        s = lcs_len(a_length - 1, b_length);
        if (t > s)
            num[a_length][b_length] = t;
        else
            num[a_length][b_length] = s;
    }
    return num[a_length][b_length];
}
//找出字符串(注意：此方法只能找出字符串中的一种)
void lcs_str(int str_len, int a_len, int b_len)
{
    if ((!a_len) || (!b_len))
        return;
    if (num[a_len][b_len] == num[a_len - 1][b_len])
        lcs_str(str_len, a_len - 1, b_len);
    else if (num[a_len][b_len] == num[a_len][b_len - 1])
        lcs_str(str_len, a_len, b_len - 1);
    else
    {
        str[str_len - 1] = a[a_len - 1];
        lcs_str(str_len - 1, a_len - 1, b_len - 1);
    }
}

仅供学习记录。