Codeforces 346B 不包含子串的LCS

题意：

给出三个字符串$s,t,virus$，求$s$和$t$的最长不包含$virus$为子串的公共子序列

方法：

设$dp[i][j][k]$为$s$的前$i$位，$t$的前$j$位所能形成的最长不包含$virus$为子串的公共子序列长度，并且这个子序列匹配$virus$到$virus$的第$k$位。

二重循环枚举$i,j$：

当$s[i]==t[j]$时：枚举$k$，显然现在的状态是从$dp[i-1][j-1][k-1]$转移而来，那么加上$s[i]$，新的匹配状态就不一定是$k$了，假设$s[i]!=virus[k]$，那么当前状态的$k$应该是$dp[i-1][j-1][k-1]$的题意子序列$+s[i]$有多长后缀与$virus$的前缀相同，此时恰恰类似$kmp$，因为从$dp[i-1][j-1][k-1]$转移来，那么$s_{[1,i-1]}$与$viru{s}_{[1,k-1]}$匹配完成，接下来就是$virus$来匹配$s[i]$，就是$kmp$的$i$=此时的$i-1$，$j=k-1$，下一步模拟$kmp$匹配即可。

$LCS$不论有没有$s[i]==t[j]$，都可以这样转移$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k],dp[i][j-1][k])$，而并非是$s[i]!=t[j]$的时候才有

题目需要输出序列，那么保存此时的决策点在哪里，输出的时候一直往上一次的决策点跳即可

#include
#define ll long long
using namespace std;

using piii=pair<int,pair<int,int>>;

int len[4],kmp[105];
int dp[105][105][105];
char ans[105][105][105];
piii last[105][105][105];
char s[105],t[105],virus[105];

piii makepii(int a,int b,int c)
{
    return make_pair(a,make_pair(b,c));
}

int main()
{
    scanf("%s%s%s",s+1,t+1,virus+1);
    len[1]=strlen(s+1);
    len[2]=strlen(t+1);
    len[3]=strlen(virus+1);
    for(int i=2,j=0;i<=len[3];i++)
    {
        while(j&&virus[j+1]!=virus[i]) j=kmp[j];
        if(virus[j+1]==virus[i]) j++;
        kmp[i]=j;
    }
    //AJKEQSLOBSROFGZ
    //OVGURWZLWVLUXTH
    //OZ     //ORZ
    //dp[i][j][k]，s的前i个，t的前j个，并且匹配完成了virus的前k个，最长的公共子序列长度
    for(int i=1;i<=len[1];i++)
    {
        for(int j=1;j<=len[2];j++)
        {
            if(s[i]==t[j])
            {
                for(int k=1,tmp;k<=len[3];k++)
                {
                    if(s[i]==virus[k]) tmp=k;
                    else
                    {
                        int now=k-1;
                        while(now&&virus[now+1]!=s[i]) now=kmp[now];
                        if(virus[now+1]==s[i]) now++;
                        tmp=now;
                    }
                    if(dp[i-1][j-1][k-1]+1>dp[i][j][tmp])
                    {
                        dp[i][j][tmp]=dp[i-1][j-1][k-1]+1;
                        ans[i][j][tmp]=s[i];
                        last[i][j][tmp]=makepii(i-1,j-1,k-1);
                    }
                }
            }
            for(int k=0;k<=len[3];k++)
            {
                if(dp[i-1][j][k]>dp[i][j][k])
                {
                    dp[i][j][k]=dp[i-1][j][k];
                    ans[i][j][k]=ans[i-1][j][k];
                    last[i][j][k]=last[i-1][j][k];
                }
                if(dp[i][j-1][k]>dp[i][j][k])
                {
                    dp[i][j][k]=dp[i][j-1][k];
                    ans[i][j][k]=ans[i][j-1][k];
                    last[i][j][k]=last[i][j-1][k];
                }
            }
        }
    }
    int max1=-1;
    for(int i=1;i<=len[1];i++)
        for(int j=1;j<=len[2];j++)
            for(int k=0;k<len[3];k++) max1=max(max1,dp[i][j][k]);
    if(max1==0) printf("0");
    else
    {
        auto print=[&](int i,int j,int k)->void
        {
            stack<char>ss;
            while(i&&j)
            {
                ss.push(ans[i][j][k]);
                auto pp=last[i][j][k];
                i=pp.first; j=pp.second.first; k=pp.second.second;
            }
            while(!ss.empty())
            {
                if(ss.top()) putchar(ss.top());
                ss.pop();
            }
            putchar('\n');
        };
        for(int i=1;i<=len[1];i++)
            for(int j=1;j<=len[2];j++)
                for(int k=0;k<len[3];k++)
                    if(dp[i][j][k]==max1){print(i,j,k);return 0;}
    }
    return 0;
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104