yeban
3/6/2012 - 10:28 AM

## find the length of longest common sequence

find the length of longest common sequence

#include <stdio.h>
#include <string.h>

int main()
{
/* read the number of test cases */
int ncases;
scanf("%d", &ncases);

int i;
for(i = 0; i < ncases; i++)
{
int m, n;

scanf("%d", &m);
char x[m];
scanf("%s", &x);

/* second string */
scanf("%d", &n);
char y[n];
scanf("%s", &y);

m = m + 1;
n = n + 1;
int lcs[m][n];
int r, c;

/* length of lcs of an empty string is 0, so fill the first row,
* and column with zero */
for(r = 0; r < n; r++)
lcs[0][r] = 0;
for(c = 1; c < m; c++)
lcs[c][0] = 0;

for(r = 1; r < m; r++)
{
for(c = 1; c < n; c++)
{
if(x[r-1] == y[c-1])
{
lcs[r][c] = lcs[r-1][c-1] + 1;
}
else if(lcs[r-1][c] >= lcs[r][c-1])
{
lcs[r][c] = lcs[r-1][c];
}
else
{
lcs[r][c] = lcs[r][c-1];
}
}
}

/*for (r = 0; r < m; r++) {*/
/*for (c = 0; c < n; c++) {*/
/*printf("%d ", lcs[r][c]);*/
/*}*/
/*printf("\n");*/
/*}*/

int lcs_length = lcs[m - 1][n - 1];

printf("CASE %d %c\n", i + 1, (lcs_length > 1 ? 'Y' : 'N'));
printf("%d\n", lcs_length);
}
}

/*
* test/input file
* 3
* 5 ddacc
* 3 cac
* 7 cbbccbc
* 4 aaca
* 4 cbeb
* 5 fdceb
*/