动态规划法
#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { string str1, str2; while (cin >> str1 >> str2) { int m = str1.length(); int n = str2.length(); int type = 1; if (m > n) { swap(m, n); type = 2; } int maxLen = 0, last = 0; vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if ((type == 1 && str1[i - 1] == str2[j - 1]) || (type == 2 && str2[i - 1] == str1[j - 1])) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLen) { maxLen = dp[i][j]; last = i; } } } } if (type == 1) { cout << str1.substr(last - maxLen, maxLen) << endl; } else { cout << str2.substr(last - maxLen, maxLen) << endl; } } }