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 n=str1.size();
        int m=str2.size();
        string str="";

        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                int len=0;
                int t=0;
                while(i+t<n && j+t<m && str1[i+t]==str2[j+t])
                {
                    ++len;
                    ++t;
                }

                if(str.size()<len)
                {
                    str = str1.substr(i,len);
                }
            }
        }

        return str;
    }
};