CF346B Lucky Common Subsequence 题解

题目链接：CF346B Lucky Common Subsequence

题意：

通过删除一个字符串中的某些元素而不改变其余元素的顺序，可以派生出该字符串的一个子序列。例如，序列 BDF 是 ABCDEF 的子序列。

字符串的子字符串是该字符串的连续子序列。 例如，BCD是ABCDEF的子串。

现在你得到了两个字符串 $s_1,s_2$ 和另一个名为 virus 的字符串。你的任务是找到 $s_1$ 和 $s_2$ 的最长公共子序列，同时不包含 virus 子字符串。

串长均小于等于 $100$ 。

升级版的最长公共子序列问题（LCS问题）

考虑增加一维，称为「与 $c$ 串的匹配度」，即：

设 $f(i,j,k)$ 表示 $a$ 串匹配到第 $i$ 位，$b$ 串匹配到第 $j$ 位，且最长公共子序列与 $c$ 串匹配到第 $k$ 位的某个串。

显然当 $a_i \ne b_j$ 时，有

$$f(i,j,k) \uparrow \max\left\{f(i,j-1,k),~f(i-1,j,k)\right\}$$

其中 $a\uparrow b$ 表示取 a = max(a, b) ，并且定义字符串 $a>b$ 当且仅当 $|a| > |b|$ 。

当 $a_i=b_j$ 时，直接去想 $f(i,j,k)$ 怎么转移不太好搞

考虑反过来想此时 $f(i-1,j-1,k)$ 的贡献

显然此时在最长公共子序列上增加一个 $a_i$ ，可能会改变匹配的程度

设加上 $a_i$ 后的最长公共子序列与 $c$ 串匹配到第 $p$ 位，则

$$f(i,j,p) \uparrow f(i-1,j-1,k) + a_i$$

其中 $+$ 表示字符串的直接拼接。

注意到这个 $p$ 可以通过跳 fail 数组得到，考虑 KMP。

时间复杂度 $O(n^3)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)
int la,lb,lc;
char a[N],b[N],c[N];
string dp[N][N][N];
int fail[N];
void proc(string &a,string b)
{
    if(a.size()<b.size())a=b;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    scanf("%s%s%s",a+1,b+1,c+1);
    la=strlen(a+1);lb=strlen(b+1);lc=strlen(c+1);
    for(int i=2,j=0; i<=lc; i++)
    {
        while(j>0&&c[i]!=c[j+1])j=fail[j];
        if(c[i]==c[j+1])++j;
        fail[i]=j;
    }
    for(int i=1; i<=la; i++)
        for(int j=1; j<=lb; j++)
            for(int k=0; k<lc; k++)
            {
                if(a[i]==b[j])
                {
                    char ch=a[i];int p=k;
                    while(p>0&&ch!=c[p+1])p=fail[p];
                    if(ch==c[p+1])++p;
                    proc(dp[i][j][p],dp[i-1][j-1][k]+ch);
                }
                proc(dp[i][j][k],dp[i][j-1][k]);
                proc(dp[i][j][k],dp[i-1][j][k]);
            }
    string res;
    for(int i=0; i<lc; i++)
        proc(res,dp[la][lb][i]);
    if(res.empty())puts("0");
    else printf("%s\n",res.c_str());
    return 0;
}

---

upd.20231226：

更新了题解的排版，并修复了一些小问题。