AT4527 LCS

Miracle_ZX · 2021-09-09 20:22:01 · 题解

Part 0

对于 LCS 不太熟悉的同学可以试着自己先学学，本文也讲得挺清楚的，可以学习一下。

求过审，谢谢啦~

upd：图床炸了，重新上传，工作量有点大（）

Part 1 LCS 的原理

LCS，顾名思义，是最长公共子序列的缩写，属于一种动态规划，如果不知道定义，建议 bdfs。话不多说，进入正题。

最长公共子序列，暴力搜索肯定是可以完成的，步骤如下所述：

枚举序列 A 里的每一个子序列 a_i；
检查子序列 a_i 是否也是 B 序列里的子序列；
在每一步记录当前找到的子序列里面的最长的子序列；

暴力法虽然好写，但是效率也非常感人。在第 1 步枚举中所有的子序列有 2^m 个，每个子序列在 B 中检查时间复杂度为 O(n)。因此最坏时间复杂度为 O(n2^m)，指数级算法，对较长的序列求LCS是不适用的，也不用想着这道题目能过，所以我们选择用动态规划来解决这个问题。

LCS 具有最有子结构的证明

这是我从 CSDN博主「GNG」搬运来的证明，也加入了我的一些思考，大家可以看一看。

令 X= <x_1,x_2,...,x_m> 和 Y=<y_1,y_2,...,y_n> 为两个序列，Z=<z_1,z_2,z_3,...,z_k> 为 X 和 Y 的任意 LCS。则：

如果 x_m = y_n，则 z_k=x_m=y_n 且 Z_{k-1} 是X_{m-1} 和 Y_{n-1} 的一个 LCS。

如果 x_m≠y_n，那么 z_k≠x_m，意味着 Z 是X_{m-1}和 Y 的一个 LCS。

如果 x_m≠y_n 那么 z_k≠y_n，意味着 Z 是 X 和 Y_{n-1} 的一个 LCS。

从上述的结论可以看出，两个序列的 LCS 问题包含两个序列的前缀的 LCS，因此，LCS 问题具有最优子结构性质。在设计递归算法时，不难看出递归算法具有子问题重叠的性质。总之，可以证明 LCS 是所有方法中最快的一种。

根据上文的叙述，LCS 的状态转移方程应该为：

LCS 的实现

LCS 的本质就是一个填表的过程，从 dp[0][0] 开始，一直到 dp[n - 1][m - 1] 结束，此题我们还要同时考虑输出路径，所以为了下文表达方便，我们不妨设：

在对应字符相等的时候，用 ↖ 标记。
在 p_1 \geq p_2 的时候，用 ↑ 标记。
在 p_1 < p_2 的时候，用←标记

于是有伪代码如下：

举个例子：我们如果要求求 ABCBDAB 和 BDCABA 的 LCS:

我当时学习 LCS 的时候，看到了这组图片演示，感觉形象了很多。如果还是不懂，现在演示一遍怎么操作 dp 数组，（以求 ABCB 和 BDCA 的 LCS 长度为例）：

啊，好累，以此类推，最后的表是：

右下角的数字 2 即为 LCS 的长度。

LCS 的路径输出

若想得到路径，则再遍历一次 dp 数组就好了，从最后一个位置开始往前遍历：

如果箭头是 ↖，则代表这个字符是 LCS 的一员，存下来后 i-- , j--

如果箭头是 ←，则代表这个字符不是LCS的一员，j--

如果箭头是 ↑，也代表这个字符不是LCS的一员，i--

如此直到 i = 0 或者 j = 0 时停止，存下来的部分即为 LCS 的路径。

Part 3 Code

代码分为两个部分：

LCS 传统板子，求出答案字符串的长度，便于遍历使用。
LCS 路径的遍历，非常基础。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int dp[1010][1010];
char s1[100010], s2[100010], ans[1000010];//两个字符串以及路径

int main()
{
    scanf("%s%s", s1 + 1, s2 + 1);
    int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
    for(int i = 1; i <= len1; i++)
    {
        for(int j = 1; j <= len2; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(s1[i] == s2[j])
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }//LCS 板子
    int i = len1, j = len2;//简单的双指针
    while(dp[i][j] > 0)
    {
        if(s1[i] == s2[j])
        {
            ans[dp[i][j]] = s1[i];//反向追踪所有的字符
            i--, j--;
        }
        else
        {
            if(dp[i][j] == dp[i - 1][j]) i--;
            else j--;
        }
    }
    printf("%s", ans + 1);//printf YYDS!
    return 0;
}

Part 3 AC Picture

731ms，49.62 MB