概念

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题,也是数据比较程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。

https://zh.wikipedia.org/wiki/最长公共子序列
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

案例

参考《算法导论》例子P222

方法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
25
/**暴力计算LCS(递归版)
 * 
 * @param  {string} word1 : 【输入】第一个字符
 * @param  {string} word2 : 【输入】第二个字符
 * @param  {int} i        : 【输入】第一个字符长度
 * @param  {int} j        : 【输入】第二个字符长度
 * @return {int}          : 【返回】LCS长度
 */
int LCSRecursion(string & word1, string & word2, int i, int j)
{
    if (i == 0 || j == 0)
    {
        return 0;
    }
    else if (word1[i - 1] == word2[j - 1])
    {
        return LCSRecursion(word1, word2, i - 1, j - 1) + 1;
    }
    else
    {

        return max(LCSRecursion(word1, word2, i - 1, j),
                   LCSRecursion(word1, word2, i, j - 1));
    }
}

方法2:动态规划DP版本(正常数组),仅计算长度。

 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
/**LCS DP版本(正常数组),仅计算长度。
 * 
 * @param  {string} word1 : 【输入】第一个字符
 * @param  {string} word2 : 【输入】第二个字符
 * @return {int}          : 【返回】LCS长度
 */
int LCSLength(string & word1, string & word2)
{
    int n = word1.length();
    int m = word2.length();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    //初始化空字符串的情况
    for (int i = 1; i <= n; ++i)
        dp[i][0] = 0;

    for (int j = 1; j <= m; ++j)
        dp[0][j] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    return dp[n][m];
}

方法3:动态规划DP版本(正常数组),计算长度和路径。

 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
/**LCS DP版本(正常数组),计算长度和路径
 * 
 * @param  {string} word1                : 【输入】第一个字符
 * @param  {string} word2                : 【输入】第二个字符
 * @param  {vector<vector<string>>} path : 【返回】路径数组
 * @return {int}                         : 【返回】LCS长度
 */
int LCSDp(string & word1, string & word2, vector<vector<string>> & path)
{
    int n = word1.length();
    int m = word2.length();

    //dp[i][j] 截止到word1前i项,word2前j项的最长的LCS长度(最优解)
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));  
    
    path.resize(n + 1, vector<string>(m + 1));

    // 初始化空字符串的情况
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 0;
    }

    for (int j = 1; j <= m; ++j)
    {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                path[i][j] = "↖";
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i - 1][j] >= dp[i][j - 1])
                {
                    path[i][j] = "↑";
                }
                else
                {
                    path[i][j] = "←";
                }
            }
        }
    }
    return dp[n][m];
}

方法4:打印输出路径(正常数组)。

 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
/**打印输出路径(正常数组)
 * 
 * @param  {vector<vector<string>>} path : 【输入】路径数组
 * @param  {string} word1                : 【输入】第一个字符
 * @param  {int} i                       : 【输入】第一个字符长度
 * @param  {int} j                       : 【输入】第二个字符长度
 */
void printLCS(vector<vector<string>> & path, string & word1, int i, int j)
{
    if (i == 0 || j == 0)
        return;

    if (path[i][j] == "↖")
    {
        printLCS(path, word1, i - 1, j - 1);
        cout << word1[i - 1] << " ";
    }
    else if (path[i][j] == "↑")
    {
        printLCS(path, word1, i - 1, j);
    }
    else
    {
        printLCS(path, word1, i, j - 1);
    }
}

方法5:DP版本(滚动数组),仅计算长度。空间复杂度优化,时间复杂度一样。

 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
/**LCS DP版本(滚动数组),仅计算长度。空间复杂度优化,时间复杂度一样
 * 
 * @param  {string} word1 : 【输入】第一个字符
 * @param  {string} word2 : 【输入】第二个字符
 * @return {int}          : 【返回】LCS长度
 */
int LCS2Length(string & word1, string & word2)
{
    int n = word1.length();
    int m = word2.length();

    int m1 = max(n, m);
    vector<vector<int>> dp(2, vector<int>(m1 + 1));

    //初始化空字符串的情况
    for (int j = 1; j <= m1; ++j)
    {
        dp[0][j] = 0;
        dp[1][j] = 0;
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (word1[i - 1] == word2[j - 1])
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
            else
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);

    return dp[n % 2][m];
}

方法6:DP版本(滚动数组),计算长度和路径。空间复杂度优化,时间复杂度一样。

 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
/**LCS DP版本(滚动数组),计算长度和路径。空间复杂度优化,时间复杂度一样
 * 
 * @param  {string} word1                : 【输入】第一个字符
 * @param  {string} word2                : 【输入】第二个字符
 * @param  {vector<vector<string>>} path : 【返回】路径数组
 * @return {int}                         : 【返回】LCS长度
 */
int LCS2Dp(string & word1, string & word2, vector<vector<string>> & path)
{
    int n = word1.length();
    int m = word2.length();
    int m1 = max(n, m);

    vector<vector<int>> dp(2, vector<int>(m1 + 1));
    path.resize(n + 1, vector<string>(m + 1));

    // 初始化空字符串的情况
    for (int j = 1; j <= m1; ++j)
    {
        dp[0][j] = 0;
        dp[1][j] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                path[i][j] = "↖";
            }
            else
            {
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);
                if (dp[(i - 1) % 2][j] >= dp[i % 2][j - 1])
                {
                    path[i][j] = "↑";
                }
                else
                {
                    path[i][j] = "←";
                }
            }
        }
    }
    return dp[n % 2][m];
}

UVA-1045 - Longest Common Subsequence

使用以上办法都可以

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int main()
{
    //UVA 10405 - Longest Common Subsequence
    while (fin.good())
    {
        string x = "";
        string y = "";

        getline(fin, x);
        getline(fin, y);

        fout << LCS2Length(x, y) << "\n";
    }
    return 0;
}

测试LCS代码

 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
int main()
{
    //算法导论例子P222
    string x = "ABCBDAB";
    string y = "BDCABA";

    vector<vector<string>> path;

    cout << setw(14) << "X: " << x << '\n';
    cout << setw(14) << "Y: " << y << '\n';
    cout << setw(14) << "LCSRecursion: ";
    cout << LCSRecursion(x, y, x.length(), y.length()) << '\n';

    cout << setw(14) << "LCSDp: " << LCS2Dp(x, y, path) << '\n';
    cout << setw(14) << "LCS: ";

    //构造LCS
    printLCS(path, x, x.length(), y.length());

    //输出过程
    cout << "\n输出过程\n";
    cout << "--------------------\n";

    cout << "  ";
    for (auto k : y)
        cout << k << " ";

    int k = 0;
    for (auto i : path)
    {
        int l = 0;
        if (k > 0)
            cout << x[k - 1] << " ";

        for (auto j : i)
        {
            if (l > 0)
                cout << j << " ";

            ++l;
        }
        cout << '\n';
        ++k;
    }
    cout << "--------------------\n";
    cout << "完成" << '\n';
    return 0;
}

测试结果