CF346B Lucky Common Subsequence

题意：
  找出字符串 \(s_1,s_2\) 的不以 \(s_3\) 为子串的最长公共子序列。（长度 \(\leq100\) ）

思路：
  如果是裸的找最长公共子序列(LCS)那么是KMP（其实这么短二维DP也行），但是若要加子串的条件的话，就应当使用DP了。可以通过DP去维护 \(s_1,s_2\) 的公共子序列有多少的长度被 \(s_3\) 匹配了，然后用KMP来找要是当前串不匹配 \(s_3\) 了的话上一个位置是在哪里。    \(dp[i][j][k]\) 表示 \(s_1\) 前 \(i\) 位 \(s_2\) 前 \(j\) 位的合条件的最长公共子序列长度是多少，此时已经匹配了 \(s_3\) 的前 \(k\) 位。（如果 \(k=len3\) 的，那该方案就要被舍弃掉啦）   关于KMP估计下周要找道裸题做做。感觉找不出好几个模板的差异，导致用起来出了差错。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
char s1[maxn], s2[maxn], s3[maxn];
int len1, len2, len3;
int dp[maxn][maxn][maxn], nex[maxn];
struct Node
{
    int x, y, z;
}pre[maxn][maxn][maxn];

inline void path(int x1, int x2, int x3, int x4, int x5, int x6)
{
    pre[x1][x2][x3].x = x4;
    pre[x1][x2][x3].y = x5;
    pre[x1][x2][x3].z = x6;
}

inline void kmp()
{
    nex[1] = 0;
    int k = 0;
    for (int i = 2; i <= len3; ++i)
    {
        while (k && s3[k + 1] != s3[i])
            k = nex[k];
        if (s3[k + 1] == s3[i])
            ++k;
        nex[i] = k;
    }
}

inline int read()
{
    int x=0;//f;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x;
}

inline void output(int x, int y, int z)
{
    if (x || y || z)
        output(pre[x][y][z].x, pre[x][y][z].y, pre[x][y][z].z);
    else
        return;
    if (dp[x][y][z] != dp[pre[x][y][z].x][pre[x][y][z].y][pre[x][y][z].z])
        printf("%c", s1[x]);
}

int main()
{
    memset(dp, -0x3f3f3f3f, sizeof dp);
    dp[0][0][0] = 0;
    scanf("%s", s1 + 1),scanf("%s", s2 + 1),scanf("%s", s3 + 1);
    len1 = strlen(s1 + 1),len2 = strlen(s2 + 1),len3 = strlen(s3 + 1);
    kmp();
    for (int i = 0; i <= len1; ++i)
        for (int j = 0; j <= len2; ++j)
            for (int k = 0; k < len3; ++k)
            {
                if (i < len1 && dp[i][j][k] > dp[i + 1][j][k])
                    dp[i + 1][j][k] = dp[i][j][k], path(i + 1, j, k, i, j, k);
                if (j < len2 && dp[i][j][k] > dp[i][j + 1][k])
                    dp[i][j + 1][k] = dp[i][j][k], path(i, j + 1, k, i, j, k);
                if (i < len1 && j < len2 && s1[i + 1] == s2[j + 1])
                {
                    int newk = k;
                    while (newk && s1[i + 1] != s3[newk + 1])
                        newk = nex[newk];
                    if (s1[i + 1] == s3[newk + 1])
                        ++newk;
                    if (dp[i + 1][j + 1][newk] < dp[i][j][k] + 1)
                        dp[i + 1][j + 1][newk] = dp[i][j][k] + 1, path(i + 1, j + 1, newk, i, j, k);
                }
            }
    int p = 0;
    for (int i = 1; i < len3; ++i)
        if (dp[len1][len2][i] > dp[len1][len2][p])
            p = i;
    if (dp[len1][len2][p])
        output(len1, len2, p);
    else
        printf("0\n");
    return 0;
}