✅创作者:陈书予
🎉个人主页:陈书予的个人主页
🍁陈书予的个人社区,欢迎你的加入: 陈书予的社区
🌟专栏地址: Java华为OD机试真题(2022&2023)
文章目录
- 1、题目描述
- 2、输入描述
- 3、输出描述
- 4、Java算法源码
- 5. 测试
- 6.解题思路
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.解题思路
- 首先读取输入的两个字符串。
- 判断哪个字符串更短,将其作为短串,另一个字符串作为长串。
- 获取短串和长串的长度。
- 初始化变量
maxLen
和start
,分别用于记录最长公共子串的长度和起始位置。 - 使用两层循环,外层循环遍历短串,内层循环遍历短串中的子串。
- 在每次内层循环中,判断当前子串是否是长串的子串,并且比较其长度是否大于之前记录的最大长度。
- 如果满足条件,更新最大长度
maxLen
和起始位置start
。 - 循环结束后,根据最大长度和起始位置在短串中提取出最长公共子串,并输出。