[算法笔记]最长公共子序列

问题介绍

最长公共子序列（Longest Common Subsequence，LCS）的解法诸多，包括但不限于蛮力法和动态规划。但是由于诸多原因，它被算作是动态规划领域的经典问题

值得注意的是，子序列≠子串

子序列未必连续，子串必然连续。

例如abcbdad和bcbd两个串的LCS是bcbd

1. LCS可能等于某个串整体
2. LCS可能有多个（不一定是唯一，但长度相同）

解析

动态规划的核心是状态转移方程，因此先给出状态转移方程：

dp[i][j]=0								// 边界条件：i=0或j=0
dp[i][j]=dp[i-1][j-1]+1					// a[i-1]=b[j-1]
dp[i][j]=MAX(dp[i][j-1],dp[i-1][j])		// a[i-1]≠b[j-1]
1
2
3

大致策略

网上的推导很多，篇幅都不短，其实就是在说一个问题，对于串A和串B和它们的最长公共子序列Z，看它们的结尾：

//结尾相同且为Z的最后一个字符
abccd
afccd
//结尾不同
abbcd
abbc
1
2
3
4
5
6

既然是动态规划，目的就是找到子问题，逐步缩减规模。这里缩减的就是串A和串B的最长公共子序列Z的长度。

显然，对于结尾有两种可能性：

1. 结尾相同且为Z的最后一个字符

abccd
afccd
// 子问题是：
abcc
afcc
1
2
3
4
5

由上，可以去掉最后一个字符得到子问题

2. 结尾不同

abbcd
abbc
// 子问题是
abbc
abbc
1
2
3
4
5

对于

abbca
abbcd
1
2

这种序列，可以先对上方串基于上述策略去除结尾，再对下方串运用相同策略去除结尾，得到：

abbc
abbc
1
2

状态转移方程解析

首先整个dp[][]啥意思。以串acbbabdbb和abcbdb为例：

整个边界给0，是方便后续的计算。

d[i][j]的意思就是串A从1到j个元素组成的串和串B从1到i个元素组成的串的LCS数值。

显然对于dp[1][j]，也就是串B的第一个字符a，无论如何和是与a还是ac还是acb…一直到acbbabdbb，其LCS都只有一个，因此不难发现第一行全为1。

然后问题扩大（其实是划分子问题的逆向过程），在B串截取出ab，该串和a或是ac或是acb…一直到acbbabdbb求取LCS

显然在这个时候多了一个b，但这时不影响，我们可以根据加上这个b之前的信息，判断现在的情况。

也就是加上这个b之前，最长子序列的情况，加上b与后面的匹配情况。

比如说在这里B串的a和A串的第一个a匹配了，这时LCS等于1，然后在它之后，b若能和A已匹配序列之后的剩余序列中的某个匹配上，就给LCS加一

显然，这时b可以和acb的最后一个字符b匹配上。所以dp[2][3]变为了2

---

再回过头来看状态转移方程：

dp[i][j]=0								// 边界条件：i=0或j=0
dp[i][j]=dp[i-1][j-1]+1					// a[i-1]=b[j-1]
dp[i][j]=MAX(dp[i][j-1],dp[i-1][j])		// a[i-1]≠b[j-1]
1
2
3

发现第三条还没讲，那就看图的dp[5][3]，即下图中标红处：

这时是B串拿abcbd和A串比较，在比到A串的第三个字符时（也就是acb），我们至少知道，B串的子串abcb和它的LCS为3。因此哪怕再给B的子串加一个，其LCS也至少为3。

// dp[5][3]表示的LCS对应的情况
acb
abcbd
// 退化为已知情况dp[4][3]
acb
abcb
1
2
3
4
5
6

如何根据dp表找序列

逆序求出，从右下角开始

int i = s2.length();
int j = s1.length();
while(i>=0 && j >= 0){
	if(dp[i][j]==dp[i-1][j]){
		i--;
	}
	else if(dp[i][j] == dp[i][j-1]){
		j--;
	}
	else{
		ret += s1[j-1];
		i--;j--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度

时间复杂度$O(mn)$

空间复杂度$O(mn)$

其中$m$、$n$分别是两个串的长度。

类似题目

[牛客]BM65 最长公共子序列(二)

class Solution {
  public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    int dp[2001][2001];
    string LCS(string s1, string s2) {
        string ret = "";
        int max = 0;
        // 边界条件置零
        for (int i = 0; i < 2001; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < 2001; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i <= s2.length(); ++i) {
            for (int j = 1; j <= s1.length(); ++j) {
                if (s1[j - 1] == s2[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1] > dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];
                }
            }
        }
        int i = s2.length();
        int j = s1.length();
        while (i >= 0 && j >= 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            } else if (dp[i][j] == dp[i][j - 1]) {
                j--;
            } else {
                ret += s1[j - 1];
                i--;
                j--;
            }
        }
        int n = ret.length();
        if(n == 0){
            return "-1";
        }
        for (int i = 0; i < n / 2; i++)
            swap(ret[i], ret[n - i - 1]);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

然后，例行自我剖析，跟大佬代码比较一下（我是说常规思路）

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        int len1 = s1.length() + 1;
        int len2 = s2.length() + 1;
        string res = "";
        vector<vector<int> > dp(len1, vector<int>(len2, 0));
        for (int i = 1; i < len1; ++i)
            for (int j = 1; j < len2; ++j)
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        int i = len1 - 1, j = len2 - 1;
        while (dp[i][j]) {
            if (dp[i-1][j] == dp[i][j-1] && dp[i][j] > dp[i-1][j-1]) {
                res += s1[i - 1];
                --i;
                --j;
            }
            else if (dp[i - 1][j] > dp[i][j - 1])  --i;
            else --j;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

它用的是vector，顺手说一下

vector<vector<int> > dp(len1, vector<int>(len2, 0));
1

使用的构造函数是

//定义具有5个整型元素的vector，且每个元素初值为2
vector<int>a(5,2);
1
2

其实就是一个置零的操作。

---

然后是另一个大佬的操作，这个效率是真的高：

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();


class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        if(s1.empty()||s2.empty()) return "-1";
        vector<vector<int> > hashTable(128,vector<int>());
        vector<int> A;
        for(int i=0;i<s1.size();i++)
            hashTable[s1[i]].push_back(i);
        for(int i=0;i<s2.size();i++)
            for(int j=hashTable[s2[i]].size()-1;j>=0;j--)
                A.push_back(hashTable[s2[i]][j]);
         
        int N = A.size(), topSize=1;
        if(!N) return "-1";
         
        vector<int> top(N,0), topIndexs(N,0), pre(N,0);
        top[0]=A[0];
        for(int i=0;i<N;i++)
        {
            if(A[i]>top[topSize-1])
            {
                pre[i] = topIndexs[topSize-1];
                top[topSize] = A[i];
                topIndexs[topSize++] = i;
            }
            else
            {
                int pos = lower_bound(top.begin(),top.begin()+topSize,A[i])-top.begin();
                if(pos) pre[i] = topIndexs[pos-1];
                top[pos]=A[i];
                topIndexs[pos]=i;
            }
        }
         
        int endIndex = topIndexs[topSize-1];
        string seq(topSize,0);
        for(int i = topSize-1,s=endIndex;i>=0;i--,s=pre[s])
            seq[i]=s1[A[s]];
         
        return seq;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59