题解 | #最长公共子串#

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,len2;
        len1 = str1.size();
        len2 = str2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i = 1;i <= len1; i++)
        {
            for(int j = 1;j<=len2;j++)
            {
                if(str1[i-1] == str2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
            }
        }
        
        int max = dp[0][0],max_i=0,max_j=0;
        for(int i = 1;i<=len1;i++)
        {
            for(int j = 1;j<=len2;j++)
            {
                if(dp[i][j]>max)
                {
                    max = dp[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
        }
        string str;
        while(max)
        {
            str = str+str1[max_i-1];
            max--;
            max_i--;
        }
        reverse(str.begin(),str.end());
        return str;
        
    }
};

和求最长公共子序列很像