@yexiaoqi
2022-05-22T09:41:35.000000Z
字数 1347
阅读 447
刷题
题目:查找两个字符串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);
}
}