题解 | #最长公共子串#

滑动窗口，同时记录最大长度位置的终止位置，最后求解子串。（题目中的优化策略很重要，就是len<Max时无需继续比较）

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    int start=0;
    int Max=0;
    string LCS(string str1, string str2) {
        // write code here
        int Max=0;
        int flag=0;
        int start1=0, start2=0;
        //移动str1
        for(int i=0;i<str1.size();i++){
            int len=min(str2.size(), str1.size()-i);
            if(len<Max){
                break;//优化
            }
            int res=getMax(str1, str2, i, len);
            if(res>Max){
                Max=res;
                start2=start;
            }
            
        }
        //移动str2
        for(int i=0;i<str2.size();i++){
            int len=min(str1.size(), str2.size()-i);
            if(len<Max){
                break;//优化
            }
            int res=getMax(str2, str1, i, len);
            if(res>Max){
                Max=res;
                start1=start;
                flag=1;
            }
        }
        //cout<<Max<<" "<<start1<<endl;
        return flag==0?str2.substr(start2-Max+1, Max):str1.substr(start1-Max+1, Max);
        
    }
    int getMax(string &str1, string &str2, int index, int len){
        int res=0;
        int max_len=0;
        for(int i=0;i<len;i++){
            //cout<<str1[index+i]<<" "<<str2[i]<<endl;
            if(str1[index+i]==str2[i]){
                res+=1;
            }
            else{
                res=0;
            }
            if(res>max_len){
                max_len=res;
                start=i;
                
            }
            //cout<<res<<" "<<Max<<endl;
        }
        return max_len;
    }
};