学步园

#define MAX 100
char x[MAX+1], y[MAX+1];
int b[MAX+1][MAX+1], c[MAX+1][MAX+1], m, n;

static void init_xy(void);
static void lcs_length(void);
static void lcs(int i, int j);
int main(int argc, char **argv)
{
        init_xy();
        lcs_length();

        printf("The lowest common subsequence is: ");
        lcs(m, n);
        printf("/n");

        return 0;
}

static void init_xy(void)
{
        int i;

        printf("Please input two sequences numbers: ");
        scanf("%d %d", &m ,&n);
        getchar();

        printf("Please input two sequences:/n");
        for(i = 1; i <= m; i++){
                scanf("%c", &x[i]);
        }
        getchar();
        for(i = 1; i <= n; i++){
                scanf("%c", &y[i]);
        }
        getchar();
}

static void lcs_length(void)
{
        int i, j;

        for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                        if(x[i] == y[j]){
                                c[i][j] = c[i-1][j-1] + 1;
                                b[i][j] = 1;
                        }
                        else if(c[i-1][j] >= c[i][j-1]){
                                c[i][j] = c[i-1][j];
                                b[i][j] = 2;
                        }
                        else{
                                c[i][j] = c[i][j-1];
                                b[i][j] = 3;
                        }
                }
        }
        printf("The lowest common subsequence lenght = %d/n", c[m][n]);
}

static void lcs(int i, int j)
{
        if(i == 0 || j == 0){
                return;
        }