c++ 动态规划 | #最长公共子串#

动态规划比双指针要慢

    string LCS2(string str1, string str2) {
	if (str1.size() == 0 || str2.size() == 0) {
        return "";
    }

    vector<vector<int>> dp(str1.size(), vector<int>(str2.size(), 0));

    int maxLen = 0, maxIndex = 0; // maxIndex 表示字符串1的索引
    for (int i = 0; i < str1.size(); i++) {
        dp[i][0] = str1[i] == str2[0] ? 1 : 0;
        if (dp[i][0] > maxLen) {
            maxLen = 1;
            maxIndex = i;
        }
    }

    for (int j = 0; j < str2.size(); j++) {
        dp[0][j] = (str1[0] == str2[j]) ? 1 : 0;
    }

    for (int i = 1; i < str1.size(); i++) {
        for (int j = 1; j < str2.size(); j++) {
            if (str1[i] == str2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }

            if (dp[i][j] > maxLen) {
                maxLen = dp[i][j];
                maxIndex = i;
            }
        }
    }

    return str1.substr(maxIndex - maxLen + 1, maxLen);	
}