codeforce Round201 div1 B. Lucky Common Subsequence KMP+DP

这种包含或不包含某串总是dp+KMP或者AC自动机，dp的状态包含KMP或者AC自动机的状态，然后利用fail指针实现转移

求KMP，在普通的最长公共子序列加一维记录匹配的状态

dp[i][j][k]记录A的i位置和B的j位置时匹配到virus的k状态的答案有多少个

wa的原因

1.如果初始化，只初始化dp[0][0][0]=0是不对的，其实本题不初始化，全部都为0没问题

2.不知道怎么记录路径，只好开个大数组记录下标，很丑陋，其实可以用一个int数为1000进制记录三个下标，

分别记录上一个状态的下标，用dfs回溯打印，但是回溯到的状态不一定都要打印，判断条件应该是转移的条件，不是A[i]=B[j]

3.当A[i]=B[j]时，也要dp[i-1][j][k]和dp[i][j-1][k]更新dp[i][j][k]，对于一些k状态不一定是dp[i-1][j-1][]+1过来的

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

char A[111],B[111],T[111];
int fail[111];
int dp[111][111][111],pre[111][111][111][3];
void getfail(char *a,int *f)
{
    int len=strlen(a);
    f[0]=f[1]=0;
    for(int i=1;i<len;++i)
    {
        int j=f[i];
        while(j&&a[j]!=a[i]) j=f[j];
        f[i+1]=a[j]==a[i]?j+1:0;
    }
}
string ans;
int depth,Len;
void dfs(int i,int j,int k)
{
    //printf("%d %d %d\n",i,j,k);
    if(pre[i][j][k][0]==i-1&&pre[i][j][k][1]==j-1) ++depth;
    if(depth<Len)
        dfs(pre[i][j][k][0],pre[i][j][k][1],pre[i][j][k][2]);
    if(pre[i][j][k][0]==i-1&&pre[i][j][k][1]==j-1) ans+=A[i];
    //if(A[i]==B[j]) ans+=A[i];
}
void update(int i,int j,int k,int ii,int jj,int kk,int add)
{
    if(dp[ii][jj][kk]==-1) return;
    if(dp[i][j][k]==-1 || dp[i][j][k]!=-1&&dp[i][j][k]<dp[ii][jj][kk]+add)
    {
        dp[i][j][k]=dp[ii][jj][kk]+add;
        pre[i][j][k][0]=ii;
        pre[i][j][k][1]=jj;
        pre[i][j][k][2]=kk;
    }
}
int main ()
{
    scanf("%s%s%s",A+1,B+1,T);
    getfail(T,fail);
    int lena=strlen(A+1);
    int lenb=strlen(B+1);
    int lenc=strlen(T);
    int nxt,kk;
    Len=0;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=lena;++i)
        for(int j=0;j<=lenb;++j)
            dp[i][j][0]=0;
    for(int i=1;i<=lena;++i)
        for(int j=1;j<=lenb;++j)
        {
            for(int k=0;k<lenc;++k)
            {
                update(i,j,k,i-1,j,k,0);
                update(i,j,k,i,j-1,k,0);
            }
            if(A[i]==B[j])
            {
                for(int k=0;k<lenc;++k)
                {
                    int nxt;
                    if(A[i]==T[k]) nxt=k+1;
                    else
                    {
                        nxt=fail[k];
                        while(nxt && T[nxt]!=A[i]) nxt=fail[nxt];
                        nxt= T[nxt]==A[i]?nxt+1:0;
                    }
                    update(i,j,nxt,i-1,j-1,k,1);
                }
            }
        }
    for(int k=0;k<lenc;++k)
        if(Len<dp[lena][lenb][k]) Len=dp[lena][lenb][kk=k];
    if(!Len) printf("0\n");
    else
    {
        depth=0;
        ans="";
        dfs(lena,lenb,kk);
        cout<<ans<<endl;
    }

    return 0;
}