HJ65. 查找两个字符串a,b中的最长公共子串

刷题

题目：查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度 1≤length≤300
进阶：时间复杂度：O(n^3)，空间复杂度：O(n)

输入描述：输入两个字符串
输出描述：返回重复出现的字符

示例：

输入：abcdefghijklmnop
     abcsafjklmnopqrstuvw
输出：jklmnop

链接：https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.next();
            String s2 = sc.next();
            String s = s1.length() > s2.length() ? s2 : s1;
            String l = s1.length() > s2.length() ? s1 : s2;
            String res = null;
            //res = longestCommSubstr1(s, l);
            res = longestCommSubstr2(s, l);
            System.out.println(res);
        }
    }
    /**
     * 从较短的字符串的全部开始截取，判断在长串中是否包含，
     * 1.如果包含，则为最长公共子串，
     * 2.如果不包含，则缩小截取的范围，从左到右依次判断
     */
    public static int longestCommSubstr2(String s, String l){
        //截取长度逐渐缩小
        for(int len=s.length(); len>0; len--){
            for (int i=0; i+len<=s.length(); i++){
                String str=s.substring(i,i+len);
                if (l.contains(str)) {
                    return str;
                }
            }
        }
        return null;
    }
    /**
     * 最多/最少等关键词，使用动态规划
     * 只有当两个字符串中的字符连续相等时最长公共字串长度才增加
     * dp[i][j]表示以s的第i个和l的第j个字符结尾的公共子串长度。
     */
    private static String longestCommSubstr2(String s, String l){
        int[][] dp=new int[s.length()+1][l.length()+1];
        int maxLen=0;
        int maxIdx=0;
        for (int i=1; i<dp.length; i++){
            for (int j=1; j<dp[0].length; j++){
                //分类讨论
                if (s.charAt(i-1)==l.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=0;
                }
                if (dp[i][j]>maxLen){
                    maxLen=dp[i][j];
                    maxIdx=i;
                }
            }
        }
        return s.substring(maxIdx-maxLen, maxIdx);
    }
}