题解 | #最长公共子串#

最长公共子序列的简化版本，字串要求必须连续。

#include <utility>
#include <vector>
class Solution {
  public:
    string LCS(string str1, string str2) {
        int len1 = str1.size(), len2 = str2.size();
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        int maxlen = 0;
        pair<int, int> maxindex;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = i * j ? dp[i - 1][j - 1] + 1 : 1;
                    if (dp[i][j] > maxlen) {
                        maxlen = dp[i][j];
                        maxindex = {i, j};
                    }
                }
            }
        }
        string res("");
        for (int k = maxindex.first, c = maxlen - 1; c >= 0;
                k--, c--) {
            res.insert(0, 1, str1[k]);
        }
        return res;
    }
};