✅创作者：陈书予
🎉个人主页：陈书予的个人主页
🍁陈书予的个人社区，欢迎你的加入: 陈书予的社区
🌟专栏地址: Java华为OD机试真题（2022&2023)

1、题目描述

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度1≤length≤300 。

2、输入描述

输入两个字符串。

3、输出描述

返回重复出现的字符。

4、Java算法源码

public static void main(String[]args){Scanner sc=new Scanner(System.in);while(sc.hasNext()){String s1=sc.nextLine();String s2=sc.nextLine();longString(s1,s2);}
}
public static void longString(String s1,String s2){String shortStr = s1.length() < s2.length() ? s1 : s2;String longStr = s1.length() > s2.length() ? s1 : s2;int shortLen = shortStr.length();int longLen = longStr.length();int maxLen = 0, start = 0;for(int i = 0; i < shortLen;i++) {// 剪枝，子串长度已经不可能超过maxLen，退出循环if(shortLen - i + 1 <= maxLen) {break;}// 左指针j，右指针k, 右指针逐渐向左逼近for(int j = i, k = shortLen; k > j; k--) {String subStr = shortStr.substring(i, k);if(longStr.contains(subStr) && maxLen < subStr.length()) {maxLen = subStr.length();start = j;// 找到就立即返回break;}}}System.out.println(shortStr.substring(start, start + maxLen));
}

5. 测试

6.解题思路

1. 首先读取输入的两个字符串。
2. 判断哪个字符串更短，将其作为短串，另一个字符串作为长串。
3. 获取短串和长串的长度。
4. 初始化变量 maxLen 和 start，分别用于记录最长公共子串的长度和起始位置。
5. 使用两层循环，外层循环遍历短串，内层循环遍历短串中的子串。
6. 在每次内层循环中，判断当前子串是否是长串的子串，并且比较其长度是否大于之前记录的最大长度。
7. 如果满足条件，更新最大长度 maxLen 和起始位置 start。
8. 循环结束后，根据最大长度和起始位置在短串中提取出最长公共子串，并输出。