题解 | #最长公共子串#

#include <vector>
class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        vector<vector<int>> dp = get_dp(str1, str2);
        int end = 0;
        int max = 0;
        for (int i = 0; i < str1.length(); ++i) {
            for (int j = 0; j < str2.length(); ++j) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        // cout << max << ", " << end << endl;
        // 从最长公共子串的下标处截取，截取长度是max
        string result = str1.substr(end - max + 1, max);
        // cout << "result == " <<  result << endl;
        return result;
    }
    
    vector<vector<int>> get_dp(string& s1, string& s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        vector<vector<int>> dp(len1, vector<int>(len2));

        // 初始化行：dp[i][0]
        for (int i = 0; i < len1; ++i) {
            dp[i][0] = s1[i] == s2[0] ? 1 : 0;
        }
        // 初始化列：dp[0][j]
        for (int j = 0; j < len2; ++j) {
            dp[0][j] = s1[0] == s2[j] ? 1 : 0;
        }

        for (int i = 1; i < len1; ++i) {
            for (int j = 1; j < len2; ++j) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return dp;
    }
};