题解 | #最长公共子串#

题目

题解：动态规划，dp[i][j]表示str1第i个字符结尾和str2第j个字符结尾时的最长公共子串长度，如果str1[i]=str2[j]，则dp[i][j]=dp[i-1][j-1]+1，并保存更新最大长度与坐标，否则dp[i][j]=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) {
        // write code here
        vector<vector<int>>dp(2,vector<int>(str2.size()+1,0));
        string res="";
        int row=1,index=0,max_len=0;
        for(int i=1;i<=str1.size();i++)
        {
            row=1-row;
            for(int j=1;j<=str2.size();j++)
            {
                if(str1[i-1]==str2[j-1])
                {
                    dp[1-row][j]=dp[row][j-1]+1;//两字符相等
                    if(dp[1-row][j]>max_len)
                    {
                        max_len=dp[1-row][j];//最大长度
                        index=i-1;//公共子串结尾坐标
                    }
                }
                else dp[1-row][j]=0;//两字符不相等
            }
        }
        return str1.substr(index-max_len+1,max_len);
    }
};