[关闭]
@yexiaoqi 2022-05-22T09:41:35.000000Z 字数 1347 阅读 447

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

刷题


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

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

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

示例

输入:abcdefghijklmnop
     abcsafjklmnopqrstuvw
输出:jklmnop

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


  1. public class Main {
  2. public static void main(String[] args) {
  3. Scanner sc = new Scanner(System.in);
  4. while (sc.hasNext()) {
  5. String s1 = sc.next();
  6. String s2 = sc.next();
  7. String s = s1.length() > s2.length() ? s2 : s1;
  8. String l = s1.length() > s2.length() ? s1 : s2;
  9. String res = null;
  10. //res = longestCommSubstr1(s, l);
  11. res = longestCommSubstr2(s, l);
  12. System.out.println(res);
  13. }
  14. }
  15. /**
  16. * 从较短的字符串的全部开始截取,判断在长串中是否包含,
  17. * 1.如果包含,则为最长公共子串,
  18. * 2.如果不包含,则缩小截取的范围,从左到右依次判断
  19. */
  20. public static int longestCommSubstr2(String s, String l){
  21. //截取长度逐渐缩小
  22. for(int len=s.length(); len>0; len--){
  23. for (int i=0; i+len<=s.length(); i++){
  24. String str=s.substring(i,i+len);
  25. if (l.contains(str)) {
  26. return str;
  27. }
  28. }
  29. }
  30. return null;
  31. }
  32. /**
  33. * 最多/最少等关键词,使用动态规划
  34. * 只有当两个字符串中的字符连续相等时最长公共字串长度才增加
  35. * dp[i][j]表示以s的第i个和l的第j个字符结尾的公共子串长度。
  36. */
  37. private static String longestCommSubstr2(String s, String l){
  38. int[][] dp=new int[s.length()+1][l.length()+1];
  39. int maxLen=0;
  40. int maxIdx=0;
  41. for (int i=1; i<dp.length; i++){
  42. for (int j=1; j<dp[0].length; j++){
  43. //分类讨论
  44. if (s.charAt(i-1)==l.charAt(j-1)){
  45. dp[i][j]=dp[i-1][j-1]+1;
  46. } else {
  47. dp[i][j]=0;
  48. }
  49. if (dp[i][j]>maxLen){
  50. maxLen=dp[i][j];
  51. maxIdx=i;
  52. }
  53. }
  54. }
  55. return s.substring(maxIdx-maxLen, maxIdx);
  56. }
  57. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注