题解 | 最长公共子串

class Solution {
public:
    string LCS(string str1, string str2) {
        int m = str1.length();
        int n = str2.length();
        
        // dp[i][j] 表示以str1[i-1]和str2[j-1]结尾的最长公共子串长度
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        int maxLen = 0;    // 记录最长公共子串的长度
        int endPos = 0;    // 记录最长公共子串在str1中的结束位置
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    
                    // 更新最长公共子串信息
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endPos = i - 1;  // 记录在str1中的结束位置
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        // 根据结束位置和长度提取子串
        if (maxLen == 0) {
            return "";
        }
        
        return str1.substr(endPos - maxLen + 1, maxLen);
    }
};

使用动态规划来解决：
定义 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 结尾的最长公共子串长度
状态转移方程：
如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
否则 dp[i][j] = 0
在填充dp表的过程中记录最长公共子串的长度和结束位置