题解 | #查找两个字符串a,b中的最长公共子串#

动态规划法

#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;
        }
    }
}