Wednesday, March 30, 2011

The Twin Towers(Longest Common Subsequence)

#include<iostream>
using namespace std;
int main()
{
int A[102],B[102],C[102][102],m,n,count=1,i,j;
void fun(int[],int[],int[][102],int,int);
for(i=0;i<102;i++)
{
C[0][i]=0;
C[i][0]=0;
}
while(cin>>m)
{
if(m==0)
{
cin>>n;
if(n==0)
{
break;
}
}
else
{
cin>>n;
for(i=1;i<=m;i++)
{
cin>>A[i];
}
for(i=1;i<=n;i++)
{
cin>>B[i];
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(A[i]==B[j])
{
C[i][j]=C[i-1][j-1]+1;
}
else
{
if(C[i][j-1]>C[i-1][j])
{
C[i][j]=C[i][j-1];
}
else
{
C[i][j]=C[i-1][j];
}
}
}
}
cout<<"Twin Towers #"<<count<<endl;
cout<<"Number of Tiles : "<<C[m][n]<<endl;
count++;
fun(A,B,C,m,n);
cout<<endl;
}
}
return 0;
}
void fun(int A[],int B[],int C[][102],int i,int j)
{
if(i==0 || j==0)
{
return;
}
else
{
if(C[i-1][j-1]==C[i][j]-1)
{
fun(A,B,C,i-1,j-1);
cout<<A[i]<<" ";
}
else if(C[i-1][j]==C[i][j])
{
fun(A,B,C,i-1,j);
}
else
{
fun(A,B,C,i,j-1);
}
}
}