CF 346B. Lucky Common Subsequence(DP+KMP)

这题确实很棒。。又是无想法。。其实是AC自动机+DP的感觉，但是只有一个串，用kmp就行了。
dp[i][j][k]，k代表前缀为virus[k]的状态，len表示其他所有状态串，处理出Ac[len][26]数组来，DP就可以了。状态转移那里一直没想清楚，wa了很多次，记录路径倒是不复杂，瞎搞搞就行。
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 char s1[103],s2[103],virus[103];
  8 int dp[103][103][103];
  9 int pre[103][103][103];
 10 int pre1[103][103][103];
 11 int Ac[111][31];
 12 int next[103];
 13 char ans[111];
 14 void kmp()
 15 {
 16     int i,j,len,temp;
 17     len = strlen(virus);
 18     next[0] = -1;
 19     j = -1;
 20     for(i = 1; i < len; i ++)
 21     {
 22         while(j >= 0&&virus[j+1] != virus[i])
 23             j = next[j];
 24         if(virus[j+1] == virus[i]) j ++;
 25         next[i] = j;
 26     }
 27     for(i = 0; i < len; i ++)
 28     {
 29         for(j = 0; j < 26; j ++)
 30         {
 31             temp = i;
 32             while(temp >= 0&&virus[temp+1] != 'A'+j)
 33                 temp = next[temp];
 34             if(virus[temp+1] == 'A' + j) temp ++;
 35             if(temp == -1)
 36                 Ac[i][j] = len;
 37             else
 38                 Ac[i][j] = temp;
 39         }
 40     }
 41     for(i = 0; i < 26; i ++)
 42     {
 43         if(i + 'A' == virus[0])
 44             Ac[len][i] = 0;
 45         else
 46             Ac[len][i] = len;
 47     }
 48 }
 49 int main()
 50 {
 51     int i,j,k,len1,len2,len,maxz,a,b,kk;
 52     scanf("%s%s%s",s1,s2,virus);
 53     len1 = strlen(s1);
 54     len2 = strlen(s2);
 55     len = strlen(virus);
 56     kmp();
 57     for(i = 1; i <= len1; i ++)
 58     {
 59         for(j = 1; j <= len2; j ++)
 60         {
 61             for(k = 0; k <= len; k ++)
 62             {
 63                 if(k == len-1) continue;
 64                 if(dp[i][j][k] < dp[i-1][j][k])
 65                 {
 66                     dp[i][j][k] = dp[i-1][j][k];
 67                     pre[i][j][k] = 2;
 68                     pre1[i][j][k] = k;
 69                 }
 70                 if(dp[i][j][k] < dp[i][j-1][k])
 71                 {
 72                     dp[i][j][k] = dp[i][j-1][k];
 73                     pre[i][j][k] = 3;
 74                     pre1[i][j][k] = k;
 75                 }
 76                 if(s1[i-1] == s2[j-1])
 77                 {
 78                     if(Ac[k][s1[i-1]-'A'] == len-1) continue;
 79                     else if(dp[i][j][Ac[k][s1[i-1]-'A']] < dp[i-1][j-1][k] + 1)
 80                     {
 81                         dp[i][j][Ac[k][s1[i-1]-'A']] = dp[i-1][j-1][k] + 1;
 82                         pre[i][j][Ac[k][s1[i-1]-'A']] = 1;
 83                         pre1[i][j][Ac[k][s1[i-1]-'A']] = k;
 84                     }
 85                 }
 86             }
 87         }
 88     }
 89     maxz = 0;
 90     for(i = 1; i <= len1; i ++)
 91     {
 92         for(j = 1; j <= len2; j ++)
 93         {
 94             for(k = 0; k <= len; k ++)
 95             {
 96                 if(maxz < dp[i][j][k])
 97                 {
 98                     maxz = dp[i][j][k];
 99                     a = i;
100                     b = j;
101                     kk = k;
102                 }
103             }
104         }
105     }
106     if(maxz == 0)
107     {
108         printf("0
");
109         return 0;
110     }
111     int num = 0;
112     //printf("%d
",maxz);
113     while(a != 0&&b != 0)
114     {
115         if(pre[a][b][kk] == 1)
116         {
117             ans[num++] = s1[a-1];
118             kk = pre1[a][b][kk];
119             a --;
120             b --;
121         }
122         else if(pre[a][b][kk] == 2)
123         {
124             kk = pre1[a][b][kk];
125             a --;
126         }
127         else if(pre[a][b][kk] == 3)
128         {
129             kk = pre1[a][b][kk];
130             b --;
131         }
132         else
133             break;
134     }
135     for(i = num-1; i >= 0; i --)
136     {
137         printf("%c",ans[i]);
138     }
139     printf("
");
140     return 0;
141 }