# ZeroJudge - d674: 10192 - Vacation
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d674
###### tags: `ZeroJudge` `動態規劃（Dynamic Programming）` `最長共同子序列（Longest Common Subsequence）`

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int LCS[102][102] = {}, timeCount = 0;
	string recommendA, recommendB;
	while (getline(cin, recommendA), recommendA != "#") {
		getline(cin, recommendB); ++timeCount;
		for (int i = 0; i != recommendA.size(); ++i)
			for (int j = 0; j != recommendB.size(); ++j)
				if (recommendA[i] == recommendB[j])
					LCS[i + 1][j + 1] = LCS[i][j] + 1;
				else
					LCS[i + 1][j + 1] = max(LCS[i + 1][j], LCS[i][j + 1]);
		cout << "Case #" << timeCount << ": you can visit at most " << LCS[recommendA.size()][recommendB.size()] << " cities.\n";
	}
}