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：

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