最长公共子序列

要求

给定两个字符串，求他们的最长公共子序列的长度。

何为最长公共子序列？

一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列，序列不要求连续，区别于最长公共子串。

例子

X = “a,b,c,f,b,c”
Y = “a,b,f,c,a,b”
X和Y的最长公共子序列为“a,b,c,b”
X和Y的最长公共子串为“a,b”

做法

递归法（不推荐，但作为一种思路）

代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int MAX(int a,int b){
    return a>b?a:b;
}
/**
 * 递归解法，时间复杂度为np，非多项式时间复杂度
 **/

int lcs_recursive(char a[],int a_length,char b[],int b_length){
    if (a_length==0||b_length==0) {
        return 0;
    }else{
        if (a[a_length-1]==b[b_length-1]) {
            return 1+lcs_recursive(a,a_length-1,b,b_length-1);
        }else{
            int a_next_length = lcs_recursive(a, a_length, b, b_length-1);
            int b_next_length = lcs_recursive(a, a_length-1, b, b_length);
            return MAX(a_next_length, b_next_length);
        }

    }
}

动态规划法(填表法)

定义一个二维数组C[i][j],记录str1(0~i)和str2(0~j)的最长公共子序列。

动态方程

if str1[i] == str2[j]
c[i][j] = c[i-1][j-1] + 1;
if str1[i] != str2[j]
c[i][j] = MAX(c[i-1][j],c[i][j-1])

代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int MAX(int a,int b){
    return a>b?a:b;
}

/**
 * 动态规划解法，时间复杂度为O(a_length*b_length)
 **/
int lcs_dp(char a[],int a_length,char b[],int b_length){
    //字符串a到a_length位置的子字符串和字符串b到b_length位置的子字符串的最长公共子序列长度
    int count[a_length+1][b_length+1];
    memset(count, 0, sizeof(count));
    for (int i=1; i<=a_length; i++) {
        for (int j=1; j<=b_length; j++) {
            int f_count1 = count[i-1][j];
            int f_count2 = count[i][j-1];
            if (a[i-1]==b[j-1]) {
                count[i][j] = count[i-1][j-1]+1;
            }else{
                count[i][j] = MAX(f_count1, f_count2);
            }
        }
    }
    return count[a_length][b_length];
}

Comments