1 #include <stdio.h>  2 #include <string.h>  3 const int N = 100 + 10;  4 int dp[N][N][N];  5 int pre[N][N][N][3];  6 char s1[N],s2[N],vir[N];  7 int next[N];  8 char ans[N];  9 void makeNext(int n) 10 { 11     next[0] = -1; 12     int i = 0,j=-1; 13     while(i < n) 14     { 15         if(j==-1 || vir[i] == vir[j]) 16         { 17             i++; 18             j++; 19             next[i] = j; 20         } 21         else 22             j = next[j]; 23     } 24 } 25 void DP(int x, int y, int z, int x1, int y1, int z1, int val) 26 { 27     if(dp[x][y][z] < dp[x1][y1][z1] + val) 28     { 29         dp[x][y][z] = dp[x1][y1][z1] + val;//状态转移 30         //保存路径 31         pre[x][y][z][0] = x1; 32         pre[x][y][z][1] = y1; 33         pre[x][y][z][2] = z1; 34     } 35 } 36 int main() 37 { 38     int i,j,k; 39     scanf("%s%s%s",s1+1,s2+1,vir); 40     int len1 = strlen(s1+1); 41     int len2 = strlen(s2+1); 42     int len3 = strlen(vir); 43     memset(dp,0,sizeof(dp)); 44     memset(pre,-1,sizeof(pre)); 45     makeNext(len3); 46     for(i=1; i<=len1; ++i) 47         for(j=1; j<=len2; ++j) 48         { 49             for(k=0; k<len3; ++k) 50             { 51                 DP(i,j,k,i-1,j,k,0);//s1[i] != s2[j]时的转移 52                 DP(i,j,k,i,j-1,k,0); 53                 if(s1[i] == s2[j])//s1[i] == s2[j] 54                 { 55                     if(s1[i] == vir[k]) 56                     { 57                         DP(i,j,k+1,i-1,j-1,k,1); 58                     } 59                     else 60                     { 61                         int p = next[k]; 62                         while(p!=-1 && s1[i] != vir[p]) p = next[p]; 63                         if(p==-1) 64                             p = 0; 65                         if(s1[i] == vir[p]) 66                             DP(i,j,p+1,i-1,j-1,k,1); 67                         else 68                             DP(i,j,p,i-1,j-1,k,1); 69                     }    70                 } 71             } 72         } 73     int z; 74     int Max = -1; 75     for(k=0; k<len3; ++k) 76         if(Max < dp[len1][len2][k]) 77         { 78             Max = dp[len1][len2][k]; 79             z = k; 80         }    81     if(Max <= 0) 82         printf("0\n"); 83     else//根据路径求出最长公共子序列 84     { 85         int tMax = Max; 86         int x = len1,y = len2; 87         while(pre[x][y][z][0] != -1) 88         { 89             int xx = pre[x][y][z][0]; 90             int yy = pre[x][y][z][1]; 91             int zz = pre[x][y][z][2]; 92             if(x-xx==1 && y-yy==1&&s1[x] == s2[y])  93                 ans[Max--] = s1[x]; 94             x = xx;y=yy;z=zz; 95         } 96         for(i=1; i<=tMax; ++i) 97             printf("%c",ans[i]); 98         printf("\n"); 99     }100 }