题解 | #最长公共子串#

动态规划，注意f[i][j] 就指的是第i，j 元素，所以到字符串索引要减去1

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 max_length = 0;
        int max_last_index = 0;

        int f[str1.length()+1][str2.length()+1];

        for(int i = 0;i<= str1.length();i++){
            f[i][0] = 0;
        }

        for(int j = 0;j<= str2.length();j++){
            f[0][j] = 0;
        }


        for(int i = 1; i<= str1.length();i++){
            for(int j = 1; j<= str2.length();j++){

                if(str1[i-1] == str2[j-1]){
                    f[i][j] = f[i-1][j-1] + 1;

                    if(f[i][j]>max_length){
                        max_length = f[i][j];
                        max_last_index = i;
                    }

                }else{
                    f[i][j] = 0;
                }
            }
        }

        return str1.substr(max_last_index - max_length, max_length);



    }
};