最长公共子子串（动态规划）

题意

给定两个字符串,求它们的最长公共子串

思路分析

公共子串

要找s1和s2的公共子串,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的后缀公共子串加上相等的字符,就能得到一个更长的公共子串, 所以有, 令s[i][j]表示分别匹配到i,j的一个公共序列

for(int i = 0; i < s1.length();i++){
    for(int j = 0;j < s2.length();j++){
        if(s1[i] == s2[j]){ // 匹配字符
            s[i][j] = s[i-1][j-1] + s1[i]; // 上一个拼接 新字符
        }else{ // 不匹配时
            s[i][j] = "";
        }
    }
}

最长证明

上述的方案中,保证了是公共的序列,但是没有控制最长

然而实际上当考虑s1的前i个和s2的前j个,如果最后一个相等,那么取它们匹配不会比不取它们匹配查,否则就是另外的偏移量的匹配了

考虑增加长度的比较,来选择更优长度的s

s对应的长度表

alt

空间优化

上述方案的缺点是,把字符串复制了一次又一次,最坏情况所有字符都记录了,总复杂度达到了 $O (n^{3})$

既然只有在s1[i]==s2[j]时才增加字符,又是子串,是连续的, 所以考虑只用记录长度, 这样最终需要答案时,直接沿着坐标倒数长度个位置,输出长度个字符即可

把上面直接记录字符串拆分成长度记录dp

dp[i][j] = s[i][j].length()

为了记录最大,新增一个变量来记录最大值的i和j

pair<int,int> maxij = {0,0}; // 最大长度的下标对应关系
// ...
if(maxij.first == 0 || dp[i+1][j+1] > dp[maxij.first][maxij.second] ){
    maxij = {i+1,j+1};
}
// ...

边界处理

这里主要的边界是运算时的边界,所以初始化其中一个长度为0时的dp为零

for(int i = 0;i<=s1.size();i++){ 
    dp[i][0] = 0;
}
for(int i = 0;i<=s2.size();i++){
    dp[0][i] = 0;
}

另一个是未计算过的值,因为要求最大值,所以未计算的值也可以设置成0 即表示长度匹配了零个有实际意义,又能参与比较

综上,直接所有长度默认初始化为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) {
        vector<vector<int> > dp(str1.size()+1,vector<int>(str2.size()+1,0)); // 记录最小值
        pair<int,int> maxij = {0,0}; // 最大长度的下标对应关系
        for(int i = 0;i < str1.size();i++){
            for(int j = 0;j < str2.size();j++){
                if(str1[i] == str2[j]){ // 相等时
                    dp[i+1][j+1] = dp[i][j]+1; // 长度
                    if(maxij.first == 0 || dp[i+1][j+1] > dp[maxij.first][maxij.second] ){
                        maxij = {i+1,j+1};
                    }
                }
            }
        }
        string res = "";
        int i = maxij.first; // s1 结束位置
        int j = maxij.second; // s2 结束位置
        for(int k = 0;k < dp[i][j];k++){ // 重构字符串
            res += str1[i-dp[i][j]+k];
        }
        return res;
    }
};

复杂度分析

空间复杂度: 状态数量是两个字符串长度之积，所以空间复杂度为 $O (n^{2})$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为 $O (n^{2})$

题解 | #最长公共子串#