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;

        /* read first string */
        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
*/