UVa 531 - Compromise

// UVa 531 - Compromise

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

string a[100];
string b[100];
int R[100][100];
bool first;

void print(int i, int j) {
	if (i < 0 || j < 0)
		return;
	if (R[i][j] == 1)
		print(i - 1, j);
	else if (R[i][j] == 2)
		print(i, j - 1);
	else {
		print(i - 1, j - 1);
		if (first)
			first = false;
		else
			cout << " ";
		cout << a[i];
	}
}

int main() {
	string word;
	while (cin >> word) {
		int m = 0;
		while (word != "#") {
			a[m++] = word;
			cin >> word;
		}
		int n = 0;
		while (cin >> word && word != "#") {
			b[n++] = word;
		}
		// LCS
		int T[100][100];
		memset(T, 0, sizeof(T));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i] == b[j]) {
					if (i == 0 || j == 0)
						T[i][j] = 1;
					else
						T[i][j] = T[i - 1][j - 1] + 1;
					R[i][j] = 3;
				} else {
					int up = (i > 0) ? T[i - 1][j] : 0;
					int down = (j > 0) ? T[i][j - 1] : 0;
					T[i][j] = max(up, down);
					R[i][j] = (up > down) ? 1 : 2;
				}
			}
		}
		// output
		first = true;
		print(m - 1, n - 1);
		cout << endl;
	}
	return 0;
}