方法1，动态规划，抄袭博客[1]：

class Solution {
public:
    string LCS(string str1, string str2) {
        // write code here
        std::string ret;
        int m=str1.size();
        int n=str2.size();
        int dp[m+1][n+1]={0};
        int start=0,mx=0;
        for(int i=0;i<m+1;i++){
            for(int j=0;j<n+1;j++){
                if(0==i||0==j) {
                    dp[i][j]=0;
                }else{
                    if(str1.at(i-1)==str2.at(j-1)){
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else{
                        dp[i][j]=0;
                    }
                    if(dp[i][j]>mx){
                        mx=dp[i][j];
                        start=i-mx;
                    }
                }
            }
        }
        ret=str1.substr(start,mx);
        return ret;
    }
};

方法2，暴力求解，抄袭博客[2]：

class Solution {
public:
    string LCS(string str1, string str2) {
        int m=str1.size();
        int n=str2.size();
        int max=0;
        int start=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int same=0;
                if(str1.at(i)==str2.at(j)){
                    same++;
                    int t=i+1;
                    int k=j+1;
                    while(t<m&&k<n&&str1.at(t)==str2.at(k)){
                        same++;
                        t++;
                        k++;
                    }
                    if(same>max){
                        max=same;
                        start=i;
                    }
                }
            }
        }

        std::string ret=str1.substr(start,max);
        return ret;
    }
};

 在牛客网中测试，方法2的运行速度和占用内存均优于方法1。

[1]动态规划——最长公共子串，没有比这更通俗易懂的了
[2]牛客BM66-最长公共子串-C++