uva 10192(最長公共子序列)

題意：求兩個字元串的最長公共子序列。

題解：最長公共子序列模闆題。。

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
const int N = 1005;
using namespace std;

int main() {
	string str1, str2;
	int f[N][N], t = 1;
	while (getline(cin, str1) && str1[0] != '#') {
		getline(cin, str2);
		int len1 = str1.size();
		int len2 = str2.size();
		memset(f, 0, sizeof(f));
		for (int i = len1; i > 0; i--)
			str1[i] = str1[i - 1];
		for (int j = len2; j > 0; j--)
			str2[j] = str2[j - 1];
		for (int i = 1; i <= len1; i++)
			for (int j = 1; j <= len2; j++) {
				if (str1[i] == str2[j])
					f[i][j] = f[i - 1][j - 1] + 1;
				else
					f[i][j] = f[i][j - 1] >= f[i - 1][j] ? f[i][j - 1] : f[i - 1][j];
			}
		printf("Case #%d: you can visit at most %d cities.\n", t++, f[len1][len2]);
	}
	return 0;
}