UVa 10405 - Longest Common Subsequence

// UVa 10405 - Longest Common Subsequence
#include <iostream>
#include <string>
using namespace std;

int main() {

	string a, b;

	while (getline(cin, a)) {
		getline(cin, b);

		int lcs[1001][1001];

		lcs[0][0] = a[0] == b[0] ? 1 : 0;
		for (int i = 1; i < a.length(); i++) {
			if (a[i] == b[0])
				lcs[i][0] = 1;
			else
				lcs[i][0] = lcs[i - 1][0];
		}
		for (int j = 1; j < b.length(); j++) {
			if (a[0] == b[j])
				lcs[0][j] = 1;
			else
				lcs[0][j] = lcs[0][j - 1];
		}

		for (int i = 1; i < a.length(); i++) {
			for (int j = 1; j < b.length(); j++) {
				if (a[i] == b[j])
					lcs[i][j] = lcs[i - 1][j - 1] + 1;
				else
					lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
			}
		}

		cout << lcs[a.length() - 1][b.length() - 1] << endl;
	}

	return 0;
}