题解 | #最长公共子串#

class Solution {
  public:
    string LCS(string str1, string str2) {
        // 首先两个字符串进行遍历
        //当两个i j指向的字符字符相等 则进入for循环中 相同字符串长度保存在k中， 只有当k > m  则进行记录 该组字符串的终止位置， m表示字符串的长度，这样就可以使得最后返回一个公共子串
        //否则不相等则j++，i只有当j == len2 - 1 的时候才进行+1
        int len1 = str1.size();
        int len2 = str2.size();
        int k = 0;
        int m = 0;
        int flag = 0;
        int i = 0, j = 0;
        while (i < len1 ) {
            if (str1[i] == str2[j]) {
                k  = 0;
                int i2 = i;
                int j2 = j;
                while (str1[i2] == str2[j2] && i2 < len1 && j2 < len2) {
                    k++;
                    if (k > m ) {
                        m = k;
                        flag = i2;
                    }
                    i2++;
                    j2++;
                }
                if (j + k >= len2) {
                    i++;
                    j = 0;
                } else j++;
            } else {
                if (j <= len2 - 2)  j++;
                if (j == len2 - 1)  {
                    j = 0;
                    i++;
                }
                k = 0;
            }
        }

        return  str1.substr(flag - m + 1, m);
    }
};