Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159

problem analysis:

First i thought of this as if s1, s2 and s3 are those three strings than if i find the lcs of s1 and s2 and again i call the same function for the lcs of (lcs of s1 and s2) and s3 than that is my answer after coding the commented down below part i found that it is not entirely true as we all know any two strings can have not single but many lcs  so if i find a lcs for the first two strings and than run it with the third one that only means that specific lcs doesn't match with the third one but there may  another lcs that matches entirely. so i had to change the whole structure  . new one is similar to the lcs of two strings just it's 3D.

Here Goes the Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. string s1, s2, s3;
4. int l1, l2, l3;
5. int dp[50+1][50+1][50+1];
6. int lcs(){
7.     memset(dp, 0, sizeof(dp));
8.     for(int i = 1; i <= l1; i++){
9.         for(int j = 1; j <=l2; j++){
10.             for(int k= 1; k <= l3; k++){
11.                 if(s1[i-1] == s2[j-1] && s2[j-1] == s3[k-1])dp[i][j][k] = 1+ dp[i-1][j-1][k-1];
12.                 else dp[i][j][k] = max(max(dp[i][j][k-1], dp[i-1][j][k]), dp[i][j-1][k]);
13.             }
14.         }
15.     }
16.     return dp[l1][l2][l3];
17. }
18. int main(){
19.     int ts;
20.     scanf("%d", &ts);
21.     for(int p = 1; p <=ts; p++){
22.     cin>>s1>>s2>>s3;
23.     l1 = s1.length();
24.     l2 = s2.length();
25.     l3 = s3.length();
26.     printf("Case %d: %d\n", p, lcs());
27.     }
28.     return 0;
29. }
30.  
31. /*
32. int lcsa(){
33.     memset(dp, 0, sizeof(dp));
34.     for(int i = 1; i <= l1; i++){
35.         for(int j = 1; j <=l2; j++){
36.             if(s1[i-1] == s2[j-1])dp[i][j] = 1+ dp[i-1][j-1];
37.             else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
38.         }
39.     }
40.    
41.     for(int i = 0; i <= l1; i++){
42.         for(int j = 0; j <= l2; j++){
43.             printf("%d ", dp[i][j]);
44.         }
45.         printf("\n");
46.     }
47.    
48.     return dp[l1][l2];
49. }
50. string ans(){
51.     int index = lcsa();
52.     char lcs[index+1];
53.    lcs[index] = '\0';
54.    int i = l1, j = l2;
55.    while (i > 0 && j > 0)
56.    {
57.       if (s1[i-1] == s2[j-1])
58.       {
59.           lcs[index-1] = s1[i-1]; // Put current character in result
60.           i--; j--; index--;     // reduce values of i, j and index
61.       }
62.     else if (dp[i-1][j] > dp[i][j-1]) i--;
63.     else j--;
64.    }
65.   string ans(lcs);
66.   return ans;
67.    
68. }
69.  
70. int main(){
71.     int ts;
72.     scanf("%d", &ts);
73.     for(int p = 1; p <=ts; p++){
74.     cin>>s1>>s2>>s3;
75.     l1 = s1.length();
76.     l2 = s2.length();
77.     s1 = ans();
78.     s2 = s3;
79.     l1 = s1.length();
80.     l2 = s2.length();
81.     printf("Case %d: %d\n", p, lcsa());
82.     }
83.     return 0;
84. }
85. */