Saturday, January 21, 2012

LCS(Longest Common Sub sequence) For Number

#include<stdio.h>
#define sz 102


int c[sz][sz], ara1[sz], ara2[sz], N1, N2;


int LCS(void)
{
int i, j;


for(i=0;i<N1;i++) c[0][i] = 0;
for(j=0;j<N2;j++) c[j][0] = 0;


for(i=1;i<=N1;i++)
for(j=1;j<=N2;j++)
{
if( ara1[i]==ara2[j] ) c[i][j] = c[i-1][j-1] + 1;


else if( c[i-1][j] > c[i][j-1] ) c[i][j] = c[i-1][j];
else c[i][j] = c[i][j-1] ;
}


return c[N1][N2];
}


int main(void)
{
int i, j, tcase=0;


while( scanf("%d%d",&N1, &N2)==2 && N1 &&N2 )
{
for(i=N1;i>0;i--)  scanf("%d",&ara1[i] );
for(i=N2;i>0;i--)  scanf("%d",&ara2[i] );


printf("Twin Towers #%d\n",++tcase);
printf("Number of Tiles : %d\n\n", LCS() );
}
}
/*
Input:
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0
Output:
Twin Towers #1
Number of Tiles : 4


Twin Towers #2
Number of Tiles : 6
*/

No comments:

Post a Comment