题解 | #最长公共子串#注意多个起点（遍历其中一个字符串，嵌套遍历第二个动态查找）

import java.util.*;
import java.lang.String;


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) {
        // write code here
        String res = "";

        //思路：遍历其中一个串 依次去尝试得到最长的串，比较保留较长的串
        for(int i =0;i<str1.length();i++){
            char cur = str1.charAt(i);
            for(int j = 0;j<str2.length();j++){
                if(str2.charAt(j)== cur){//注意可能有多个
                    String curStr = getMaxLength(str1,str2,i,j);
                    res = res.length() > curStr.length() ? res : curStr;
                }
            }
        }
        return res;
    }

    public String getMaxLength(String s1,String s2,int i,int j){

        String result = "";

        while(i <s1.length() && j < s2.length()){
            char next = s1.charAt(i);
            if(next == s2.charAt(j)){
                result += next;
                i ++;
                j ++;
            } else {
                return result;
            }
        }
        return result;
    }
}