#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	// your code goes here
	string sa = "abdc", sb = "adc";
	vector<vector<int>> dp(sa.size()+1, vector<int>(sb.size()+1));
 
	for (int i=1;i<=sa.size();i++) {
		for (int j=1;j<=sb.size();j++) {
			if (sa[i-1] == sb[j-1]) {
				dp[i][j] = dp[i-1][j-1] + 1;
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	cout<<dp[sa.size()][sb.size()]<<endl;
	int k = dp[sa.size()][sb.size()];
	return k - sa.size() == 1 || k - sb.size() == 1; 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglzdHJpbmcgc2EgPSAiYWJkYyIsIHNiID0gImFkYyI7Cgl2ZWN0b3I8dmVjdG9yPGludD4+IGRwKHNhLnNpemUoKSsxLCB2ZWN0b3I8aW50PihzYi5zaXplKCkrMSkpOwoKCWZvciAoaW50IGk9MTtpPD1zYS5zaXplKCk7aSsrKSB7CgkJZm9yIChpbnQgaj0xO2o8PXNiLnNpemUoKTtqKyspIHsKCQkJaWYgKHNhW2ktMV0gPT0gc2Jbai0xXSkgewoJCQkJZHBbaV1bal0gPSBkcFtpLTFdW2otMV0gKyAxOwoJCQl9IGVsc2UgewoJCQkJZHBbaV1bal0gPSBtYXgoZHBbaS0xXVtqXSwgZHBbaV1bai0xXSk7CgkJCX0KCQl9Cgl9Cgljb3V0PDxkcFtzYS5zaXplKCldW3NiLnNpemUoKV08PGVuZGw7CglpbnQgayA9IGRwW3NhLnNpemUoKV1bc2Iuc2l6ZSgpXTsKCXJldHVybiBrIC0gc2Euc2l6ZSgpID09IDEgfHwgayAtIHNiLnNpemUoKSA9PSAxOyAKCXJldHVybiAwOwp9