华为机试-HJ65 查找两个字符串a,b中的最长公共子串

日常刷题记录，欢迎讨论交流。

牛客网题目链接：https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506

描述

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
 
数据范围：字符串长度1≤length≤300 
进阶：时间复杂度：O(n^3)/O(n3) ，空间复杂度：O(n)/O(n) 

输入描述：

输入两个字符串

输出描述：

返回重复出现的字符

示例1

输入：

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出：

jklmnop

解法一：

　　先判断输入的两个字符串长短，从短的字符串中取出子串然后依次查找是否属于长串的字段，取子串要按从左到右的顺序取，因为不排除会存在两个相同长度的子串，而题目要求只输出最先出现的。这种解法属于不断枚举判断，时间复杂度比较大。

 1 import java.util.Scanner;
 2 import java.util.List;
 3 import java.util.ArrayList;
 4 
 5 public class Main{
 6     public static void main(String[] args){
 7         Scanner sc = new Scanner(System.in);
 8         String str1 = sc.nextLine();
 9 //         System.out.println(str1);
10         String str2 = sc.nextLine();
11 //         System.out.println(str2);
12         String strlong = "";
13         String strshort = "";
14         if(str1.length() > str2.length()){
15             strlong = str1;
16             strshort = str2;
17         }else{
18             strlong = str2;
19             strshort = str1;
20         }
21         String strtemp = "";
22         int maxlen = 0;
23         List<String> list = new ArrayList<>();
24         for(int i = 0; i < strshort.length() && strshort.length()-i > maxlen; i++){
25             for(int j = strshort.length(); j > i; j--){
26                 strtemp = strshort.substring(i,j);
27                 if(strlong.indexOf(strtemp) >= 0){
28                     list.add(strtemp);
29                     break;//找到子串就退出，因为后面的串即使是子串也不是最长的（即遍历一趟最多记录一个最长子串）
30                 }
31             }
32             maxlen = Math.max(maxlen,strtemp.length());//记录最长子串长度
33         }
34 //         System.out.println("maxlen: "+maxlen);
35 //         System.out.println("list: "+list.toString());
36         for(String substr : list){
37             if(substr.length() == maxlen){
38                 System.out.println(substr);
39                 break;
40             }
41         }
42     }
43 }