Codeforces Round#201(div1) D. Lucky Common Subsequence

题意：给定两个串，求出两个串的最长公共子序列，要求该公共子序列不包含virus串。

用dp+kmp实现

dp[i][j][k]表示以i结尾的字符串和以j结尾的字符串的公共子序列的长度（其中k表示该公共子序列的与virus的匹配程度）很显然，当k==strlen(virus)时，该公共子序列不是我们所求得

当添加一个字符时，如果失配，这时不能让k直接等于0，而是要用kmp给k一个合理的值。

 #include <stdio.h>

 #include <string.h>

 const int N =  + ;

 int dp[N][N][N];

 int pre[N][N][N][];

 char s1[N],s2[N],vir[N];

 int next[N];

 char ans[N];

 void makeNext(int n)

 {

     next[] = -;

     int i = ,j=-;

     while(i < n)

     {

         if(j==- || vir[i] == vir[j])

         {

             i++;

             j++;

             next[i] = j;

         }

         else

             j = next[j];

     }

 }

 void DP(int x, int y, int z, int x1, int y1, int z1, int val)

 {

     if(dp[x][y][z] < dp[x1][y1][z1] + val)

     {

         dp[x][y][z] = dp[x1][y1][z1] + val;//状态转移

         //保存路径

         pre[x][y][z][] = x1;

         pre[x][y][z][] = y1;

         pre[x][y][z][] = z1;

     }

 }

 int main()

 {

     int i,j,k;

     scanf("%s%s%s",s1+,s2+,vir);

     int len1 = strlen(s1+);

     int len2 = strlen(s2+);

     int len3 = strlen(vir);

     memset(dp,,sizeof(dp));

     memset(pre,-,sizeof(pre));

     makeNext(len3);

     for(i=; i<=len1; ++i)

         for(j=; j<=len2; ++j)

         {

             for(k=; k<len3; ++k)

             {

                 DP(i,j,k,i-,j,k,);//s1[i] != s2[j]时的转移

                 DP(i,j,k,i,j-,k,);

                 if(s1[i] == s2[j])//s1[i] == s2[j]

                 {

                     if(s1[i] == vir[k])

                     {

                         DP(i,j,k+,i-,j-,k,);

                     }

                     else

                     {

                         int p = next[k];

                         while(p!=- && s1[i] != vir[p]) p = next[p];

                         if(p==-)

                             p = ;

                         if(s1[i] == vir[p])

                             DP(i,j,p+,i-,j-,k,);

                         else

                             DP(i,j,p,i-,j-,k,);

                     }

                 }

             }

         }

     int z;

     int Max = -;

     for(k=; k<len3; ++k)

         if(Max < dp[len1][len2][k])

         {

             Max = dp[len1][len2][k];

             z = k;

         }

     if(Max <= )

         printf("0\n");

     else//根据路径求出最长公共子序列

     {

         int tMax = Max;

         int x = len1,y = len2;

         while(pre[x][y][z][] != -)

         {

             int xx = pre[x][y][z][];

             int yy = pre[x][y][z][];

             int zz = pre[x][y][z][];

             if(x-xx== && y-yy==&&s1[x] == s2[y])

                 ans[Max--] = s1[x];

             x = xx;y=yy;z=zz;

         }

         for(i=; i<=tMax; ++i)

             printf("%c",ans[i]);

         printf("\n");

     }

 }