?
思路：LCS
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; char s[205]; char t[205]; int dp[205][205]; int main() { while(scanf(%s %s, s + 1, t + 1) != EOF) { int ls = strlen(s + 1); int lt = strlen(t + 1); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= ls; i ++) { for(int j = 1; j <= lt; j ++) { if(s[i] == t[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } cout << dp[ls][lt] << endl; } return 0; }