题解 | #最长公共字串#

字串和子序列不同，一旦中间一个不等，其当前长度最长公共字串就要变为0.

同时记录下公共字串的最大值以及对应的字符串末尾下标。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
  //  字串要求字符在源对象中连续，而序列只保证相对顺序不变
    string LCS(string str1, string str2) {
      if (str1.empty() || str2.empty()) {
        return "";
      }
      
      int len1 = str1.size(), len2 = str2.size();
      int max = 0, pos = 0;
      
      std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1, 0));
      
      for (int i = 0; i < len1; ++i) {
        for (int j = 0; j < len2; ++j) {
          dp[i + 1][j + 1] = str1[i] == str2[j] ? dp[i][j] + 1 : 0;
          if (dp[i + 1][j + 1] > max) {
            max = dp[i + 1][j + 1];
            pos = i;
          }
        }
      }
      
      return str1.substr(pos - max + 1, max);
    }
};