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 (str1.size(), vector<int> (str2.size(),0));
        int a = 0;
        int b = 0;
        int res = 0;
        for(int i = 0; i < str1.size(); i++)
               for(int j = 0; j < str2.size(); 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]>res){
                           res = dp[i][j];
                           a = j-res;
                           b = j;
                       }
                   }
                   else{
                       dp[i][j] = 0;
                   }
               }
        return str2.substr(a+1, res);
    }
};