题解 | #最长公共子串#

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        //最长的公共子序列，初始化序列
        vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1,0));
        int res = 0;
        int pos = 0;
        for(int i = 1; i <= s1.size() ; i++)
        {
            for(int j = 1; j <= s2.size(); j++)
            {
                if(s1[i - 1] == s2[j - 1])
                {
                    //怎么会呢，就差在后面的一个+1上面,只要确定斜对角是相等的即可
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //这里面就需要对维护的最大值进行更新，以保障得到的用户一直处于最后的位子
                    if(res <= dp[i][j])
                    {
                        res = dp[i][j];
                        pos = i;//代表最后终止的地方
                    }
                }
                //不相等的话直接置零即可
                else{
                    dp[i][j] = 0;
                }
            }
        }
        
        string r;
        //截取当前子序列的值，然后处理即可
        r.assign(s1.begin() + pos - res , s1.begin() + pos);
        std::cout << r << " res = " << res << " pos = " << pos << std::endl;
        if(r.size() == 0) return "-1";
        return r;
    }
};