题解 | #最长公共子串#

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        int start = 0;
        int end = 1; //初始条件：subString(0, 1)，左闭右开，即只取第一个第0个字符
        String result = "";
        while(end <= str2.length()){ //subString左闭右开，所以可以取到等于
            String subStr = str2.substring(start, end);
            if(str1.contains(subStr)){
                result = subStr; // str1包含str2的该子串，例如:ab，继续右移看是否继续包含abc，所以end右移
            }else{
                start++; //str1不包含str2的该子串，例如:13，不必再找以13开头的子串了，因为不包含13，肯定也不包含134，所以start右移；因为需要找最长子串，start右移后，end也需要右移，保证长度不会缩短
            }
            end++; //上述两种情况，均需要end右移
        }
        return result;
    }
}