//根据LCS的最优子结构定理可得转移方程 /* 0 i == 0 || j == 0 len[i][j] = len[i - 1][j - 1] + 1 s1[i] == s2[j] max(len[i - 1][j], len[i][j - 1]) s1[i] != s2[j] */ #include <iostream> #include <cstring> #include <algorithm> #include <string> using namespace std; int len[1000][1000]; string s1, s2; int main() { //freopen("1.txt", "r", stdin); while(cin >> s1 >> s2) { memset(len, 0, sizeof(len)); for(int i = 1; i <= s1.size(); i++) { for(int j = 1; j <= s2.size(); j++){ if(s1[i - 1] == s2[j - 1]) len[i][j] = len[i - 1][j - 1] + 1; else len[i][j] = max(len[i - 1][j], len[i][j - 1]); } } cout << len[s1.size()][s2.size()] << endl; } return 0; }
