题解 | #最长公共子串#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int len1 = str1.size();
        int len2 = str2.size();

        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        vector< vector<int>> assit(len1+1, vector<int>(len2+1, 0));

        int assitI = 0, assitJ = 0, maxAssit = 0;

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1[i-1] == str2[j-1]) {
                    int op1 = dp[i-1][j-1];
                    assit[i][j] = assit[i-1][j-1] + 1;
                    if (assit[i][j] > maxAssit) {
                        assitI = i;
                        assitJ = j;
                        maxAssit = assit[i][j];
                    }
                    int op2 = assit[i][j];
                    dp[i][j] = op1 > op2 ? op1 : op2;
                } else {
                    int op1 = dp[i-1][j];
                    int op2 = dp[i][j-1];
                    dp[i][j] = op1 > op2 ? op1 : op2;
                }
            }
        }

        string res;
        while (maxAssit--) {
            res = str1[--assitI] + res; 
        }

        return res;
    }
};

两个二维数组，dp[i][j]记录包括str1第i个字母，str2第j个字母的两个字符串最大子串的长度。assit[i][j]则记录两个字符串在当前位置相同后缀的长度。转移方程为如果str1[i-1] == str2[j-1](记住str的下标是从0开始的）则dp[i][j] = max ( dp[i-1][j-1], assit[i-1][j-1] + 1). 若str1[i-1] != str2[j-1]，则dp[i][j] = max ( dp[i-1][j], dp[i][j-1])。最后再额外用一组变量记录最大连续后缀长度的所在位置，就能很方便的进行遍历了。