1447.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1447 on 2005-09-19 at 19:10:44 */ 
#include <stdio.h>
#include <string.h>

int b[101][101], flag;
char x[101][31], y[101][31];

void lcs(int, int);

int main()
{
    char a[101][101], ch;
    int n, m;
    int i, j;
    
	while(1) {
	    i = 0;
	    while(1) {
	        ch = getchar();
	        if(ch == EOF) {
	            return 0;
	        } else if(ch != ' ' && ch != '\n' && ch != '\t') {
	            x[0][i++] = ch;
	        } else {
	            break;
	        }    
	    }
	    x[0][i] = 0;
		for(n = 1; n < 101; n++) {
			scanf("%s", x[n]);
			if(!strcmp(x[n], "#")) {
				break;
			}
		}
		for(m = 0; m < 101; m++) {
			scanf("%s", y[m]);
			if(!strcmp(y[m], "#")) {
				break;
			}
		}
		while(getchar() != '\n')
			;
		for(i = 0; i <= n; i++) {
			for(j = 0; j <= m; j++) {
				if(i == 0 || j == 0) {
					a[i][j] = 0;
				} else {
					if(!strcmp(x[i-1], y[j-1])) {
						a[i][j] = a[i-1][j-1] + 1;
						b[i][j] = 1;
					} else {
						if(a[i][j-1] < a[i-1][j]) {
							a[i][j] = a[i-1][j];
							b[i][j] = 2;
						} else {
							a[i][j] = a[i][j-1];
							b[i][j] = 3;
						}    
					}
				}
			}
		}
		flag = 0;
		lcs(n, m);
		putchar('\n');
	}
    
    return 0;
}

void lcs(int i, int j)
{
    if(i == 0 || i == 0) {
        return;
    }
    if(b[i][j] == 1) {
        lcs(i-1, j-1);
        if(flag == 1) {
            putchar(' ');
        }
        printf("%s", x[i-1]);
        flag = 1;
    } else if(b[i][j] == 2) {
        lcs(i-1, j);
    } else {
        lcs(i, j-1);
    }    
}