题解 | 最长公共子串

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // 先填充一个二位数组，并实时用一个max记录数组中的最大位置。
        int len1 = str1.length(), len2 = str2.length();
        int maxnum = 0, maxi = 0, maxj = 0;
        string ans;
        vector<vector<int>>dp(len1+1, vector<int>(len2+1, 0));
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = 0;
                }
                if(dp[i][j]>maxnum){
                    maxi = i;
                    maxj = j;
                    maxnum = dp[i][j];
                }
            }
        }
        while(maxnum>0){
            ans += str1[maxi-1];
            maxi--;
            maxj--;
            maxnum--;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

学会了最长子序列，最长子串也非常简单了！