CF346B Lucky Common Subsequence 题解

题目链接：

题意：通过删除一个字符串中的某些元素而不改变其余元素的顺序，可以派生出该字符串的一个子序列。 例如，序列BDF是ABCDEF的子序列。 字符串的子字符串是该字符串的连续子序列。 例如，BCD是ABCDEF的子串。 你得到了两个字符串s1,s2和另一个名为virus的字符串。你的任务是找到s1和s2的最长公共子序列，同时不包含virus子字符串。

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

考虑增加一维，称为与 c c c 串匹配度，即

d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示：

a a a 串匹配到第 i i i 位， b b b 串匹配到第 j j j 位最长公共子序列与 c c c 串匹配到第 k k k 位。

显然当 a [ i ] ≠ b [ j ] a[i] e b[j] a[i]=b[j] 时，有 d p [ i ] [ j ] [ k ] = max ⁡ ( d p [ i ] [ j ] [ k ] , d p [ i ] [ j − 1 ] [ k ] , d p [ i − 1 ] [ j ] [ k ] ) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k],dp[i-1][j][k]) dp[i][j][k]=max(dp[i][j][k],dp[i][j−1][k],dp[i−1][j][k])

当 a [ i ] = b [ j ] a[i]=b[j] a[i]=b[j] 时，直接去想 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 怎么转移不太好搞

考虑反过来想此时 d p [ i − 1 ] [ j − 1 ] [ k ] dp[i-1][j-1][k] dp[i−1][j−1][k] 的贡献

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

设加上 a [ i ] a[i] a[i] 后的最长公共子序列与 c c c 串匹配到第 p p p 位

则有 d p [ i ] [ j ] [ p ] = d p [ i ] [ j ] [ p ] , d p [ i − 1 ] [ j − 1 ] [ k ] + a [ i ] dp[i][j][p] = dp[i][j][p],dp[i-1][j-1][k]+a[i] dp[i][j][p]=dp[i][j][p],dp[i−1][j−1][k]+a[i]

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

则时间复杂度 O ( n 3 ) O(n^3) O(n3)

#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
",res.c_str());
    return 0;
}