题解 | #最长公共子串#

我的代码比较简单，希望能帮到大家
以两个字符串的长度，构造一个二维数组，然后遍历两个字符串进行匹配，如果相等，则将二维数组中的数据置1.
最终获取二维数组斜长最大的那份数据，就是最长的公共子串。

public String LCS(String str1, String str2) {
    int[][] arr = new int[str1.length()][str2.length()];
    int start = 0, end = 0, max = 0;
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                arr[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            if (arr[i][j] == 1) {
                int m = 1, ii = i + 1, jj = j + 1;
                while (ii < str1.length() && jj < str2.length()) {
                    if (arr[ii][jj] == 1) {
                        m++;
                        ii++;
                        jj++;
                    } else {
                        break;
                    }
                }
                if (m > max) {
                    start = i;
                    end = ii;
                    max = m;
                }
            }
        }
    }
    return str1.substring(start, end);
}