题解 | #最长公共子串#

动态规划方法：
首先使用二维数组dp，确定其元素dp[i][j]的含义（此处指str1的第i个元素和str2的第j个元素为结尾的最长公共子串长度，注意最后一个元素必然是相同的）。
然后找到状态转移方程：若新加入元素相同，则在原长度加一，即dp[i][j]=dp[i-1][j-1]+1,否则为0。接着考虑dp数组的初始化即边界条件。
最后由于要返回最长公共子串序列，而dp数组只记录了其长度数值，故需要确定最大长度，即dp数组最大值，以及公共子串的结尾标志，通过结尾标志和子串长度回到原字符串中寻找公共子串。

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 maxLen=0;
        int maxLastind=0;
        int dp[str1.length()][str2.length()];
        dp[0][0]=0;//初始化
        for(int i=0;i<str1.length();++i)
        {
            for(int j=0;j<str2.length();++j)
            {
                if(str1[i]==str2[j])
                {
                    if(i==0 || j==0)
                    {//边界条件
                        dp[i][j]=1;
                    }
                    else
                    {//状态转移方程
                        dp[i][j]=dp[i-1][j-1]+1;
                        if(dp[i][j]>maxLen)
                        {//确定最长公共子串的长度与结束标志
                            maxLen=dp[i][j];
                            maxLastind=i;
                        }
                    }
                }
                else
                    dp[i][j]=0;
            }
        }
        return str1.substr(maxLastind-maxLen+1,maxLen);
        */




        //优化：使用一维数组
        int maxLen=0;
        int maxLastind=0;
        vector<int> dp(str2.length(),0);
        for(int i=0;i<str1.length();++i)
        {
            for(int j=str2.length()-1;j>=0;--j)
            {//注意必须是倒序，因为原本需要用到左上角元素值，故从右往左进行
                if(str1[i]==str2[j])
                {
                    if(i==0 || j==0)
                    {
                        dp[j]=1;
                    }
                    else
                    {
                        dp[j]=dp[j-1]+1;
                        if(dp[j]>maxLen)
                        {
                            maxLen=dp[j];
                            maxLastind=j;
                        }
                    }
                }
                else
                    dp[j]=0;
            }
        }
        return str2.substr(maxLastind-maxLen+1,maxLen);    
    }
};