1159 - Batman

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

Batman is in deep trouble. You know that superheroes are there to help you when you are in trouble. But in Gotham city there is no trouble. So, 'no trouble' is actually the trouble for our Batman.

So, Batman is trying to solve ACM problems because he wants to be a good programmer like you :). But alas! He is not that smart. But still he is trying. He found 3 strings of characters. Now he wants to find the maximum string which is contained in all the three strings as a sub sequence. He wants to find the maximum length, not the sequence.

Now, Batman claims that he is a better programmer than you. So, you are solving the same problem. Can you solve faster? You are guaranteed that Batman will need 3 hours to solve the problem. So, you have to be faster than him.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case will contain a blank line and three strings in three lines. None of the string lengths will be greater than 50 and less than 1. And the string will contain alphanumeric characters only.

Output

For each case, print one line containing the case number and the length of the largest subsequence.

Sample Input	Output for Sample Input
3 abcdef cdef dcdef aaaa bbbb ccca aaaa aaaa aaa	Case 1: 4 Case 2: 0 Case 3: 3

        

This is a standard lca question extended to 3d state 

after visualising it we shall observe that  

if(a[i]==b[j]==c[k])

dp[i][j][k]=1+dp[i-1][j-1][k-1]

else the normal recurrence is

 dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k]),dp[i][j][k-1]);

               ******************The code goes here *******************************

#include<bits/stdc++.h>

using namespace std;

int dp[56][56][56];

int main()

{

  int t;

  cin>>t;

  int tt=1;

  while(t--)

  {

   string a,b,c;

   cin>>a>>b>>c;

   int n=a.length();

   int m=b.length();

   int l=c.length();

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;i++)

   {

        for(int j=1;j<=m;j++)

 {

    for(int k=1;k<=l;k++)

{

if(a[i-1]==b[j-1] && a[i-1]==c[k-1])

{

          dp[i][j][k]=1+dp[i-1][j-1][k-1];

}

else 

{

      /* if(a[i-1]==b[j-1])

       {

           dp[i][j][k]=1+dp[i-1][j-1][k];

}

if(a[i-1]==c[k-1])

{

   dp[i][j][k]=1+dp[i-1][j][k-1];

}

if(b[j-1]==c[k-1])

{

 dp[i][j][k]=1+dp[i][j-1][k-1];

}*/

// if((a[i-1]!=b[j-1]) &&(a[i-1]!=c[k-1]) &&(b[j-1]!=c[k-1]))

{

 dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k]),dp[i][j][k-1]);

}

}

}

}

}

cout<<"Case "<<tt<<": "<<dp[n][m][l]<<endl;

                tt++;

}

return 0;

}