题解 | #NC92-最长公共子串#

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        vector<vector<int>> maxLen(s1.size() + 1, vector<int>(s2.size() + 1, 0)); // 增加外圈0，方便讨论边界
        int str_len = 0, str_end_idx = 0; // 记录最长子串长度及结束index
        for (int i = 0; i < s1.size(); i++)
            for (int j = 0; j < s2.size(); j++) {
                if (s1[i] == s2[j]) {
                    maxLen[i + 1][j + 1] = maxLen[i][j] + 1;
                    if (maxLen[i + 1][j + 1] > str_len) {
                        str_len++;
                        str_end_idx = i;
                    } // 当有很多个子串时，找最长的那个
                       
                }

                else
                    maxLen[i + 1][j + 1] = 0; // 构建最小公共子串的长度矩阵，0表示该元素不在子串内
            }
//         for (int i = 0; i < s1.size(); i++) {
//             for (int j = 0; j < s2.size(); j++)
//                 cout << maxLen[i + 1][j + 1] << " ";
//             cout << endl;
//         }
        return s1.substr(str_end_idx - str_len + 1, str_len);
    }
};