【牛客刷题18】 查找两个字符串a,b中的最长公共子串_编程题 两个字符串的公共子串

一、题目

题目链接：查找两个字符串a,b中的最长公共子串

二、 题目分析

两种思路，第一种常规思路，第二种动态规划。

1.常规思路一

  通过遍历两个字符串str1与str2，同时维护左右两个指针，判断出重复最长的字符串即可。

1. 遍历较短字符串的每个字符作为起点，不断进行子串的匹配
2. 维护 左指针j，右指针k, 右指针逐渐向左逼近
3. 满足子串匹配的同时还要满足子串长度是最大的

import java.util.*;
public class Main{
    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            //判断两个字符串谁长谁短
            if (str1.length() <= str2.length()) {
                longString(str1, str2);
            } else {
                longString(str2, str1);
            }
        }
    
    public static void longString(String str1,String str2){
        //定义最大长度maxLen ，开始下标start
        int maxLen = 0;
        int start = 0;
        for(int i = 0;i<str1.length();i++){
            if(str1.length()-i-1 <= maxLen){
                break;
            } 
            for(int j =i,k=str1.length(); k>j ;k--){
                String subStr = str1.substring(i,k);
                if(str2.contains(subStr) && maxLen<subStr.length()){
                    maxLen = subStr.length();
                    start = j;
                    break;
                }
            }
        }
        System.out.println(str1.substring(start,start+maxLen));
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2.常规思路2

  利用StringBuilder ，把短了的字符串str1放到StringBuilder 中，然后遍历长的字符str2，判断str2当中有无StringBuilder的字符，若有，将StringBuilder的字符更新到result，直到找到最长的公共字符串。实际与常规思路1类似。

import java.util.*;
public class Main{
    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            //判断两个字符串谁长谁短
            if (str1.length() <= str2.length()) {
                longString(str1, str2);
            } else {
                longString(str2, str1);
            }
        }

ublic static void compare(String str1, String str2) {
            String result = "";
            for(int i =1;i<str1.length();i++){
                StringBuilder stringBuilder = new StringBuilder();
                for(int j =i-1;j<str1.length();j++){
                    if(str2.contains(stringBuilder.append(str1.charAt(j)))){
                        if(stringBuilder.length() > result.length()){
                            result = stringBuilder.toString();
                        }
                    }
                }
        }
        System.out.println(result);
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

3.动态规划思路

  简单介绍一下动态规划。动态规划采用分治的思想将问题化解。把大问题化成小问题，再用小问题推导大问题的解。它有四个要素：

1. 状态 ，问题中的抽象状态
2. 状态转移方程
3. 状态初始化
4. 返回值

  这道题我们需要先把状态找出来。我们的问题是：两个字符中的最长共同子串。

  子问题则是：a的子串和b的子串中的最长共同子串
  抽象子问题：a的前i个字符和b的前j个字符中，它们最长共同子串。

  如果我们要知道最长共同子串的具体内容，则需要知道长度，起始位置，结束位置。因此我们的状态如下：

F（i,j） :以a的第i个字符结尾的子串和以b的第j个字符结尾的子串，它们的最长共同子串长度。

  我们举个例子：

字符串a：abcabcde
字符串b：abcd

  下面我们通过画图来阐述：

图片）

  通过上面的分析，可以发现，如果a的第i个字符和b的第j个字符相同，则:

相同：F(i，j) = F(i - 1, j- 1)+1，这个实际上就是我们的转移方程。
不相同：0

  那么我们的初始状态与返回值是什么？

初始状态F(0,0) = 0
返回值：最长子串的内容

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        //判断两个字符串谁长谁短
        if (str1.length() <= str2.length()) {
            longString(str1, str2);
        } else {
            longString(str2, str1);
        }
    }
    
    public static void longString(String str1,String str2){
        char[]arr1 = str1.toCharArray();
        char[]arr2 = str2.toCharArray();
        int len1 = arr1.length;
        int len2 = arr2.length;
        //定义最大长度maxLen ，开始下标start
        int maxLen = 0;//最长子串的长度
        int start = 0;//最长子串的起始位置
        int[][] maxSubLen = new int[len1+1][len2+1];
        for(int i = 1;i<=len1;i++){
            for(int j =1;j<=len2;j++){
                //如果第i个字符与第j个字符相等，则进行累加
                if(arr1[i-1] == arr2[j-1]){
                    maxSubLen[i][j] = maxSubLen[i-1][j-1]+1;
                    //更新
                    if(maxLen < maxSubLen[i][j]){
                        maxLen = maxSubLen[i][j];
                        start = i - maxLen;
                    }
                }
            }
        }
        System.out.println(str1.substring(start,start+maxLen));
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

三、最后

  学习最怕的就是没有收获，其实有时候想想会很奇怪，如果我们不学本就没有收获，如果我们学了，可能会有收获，那为何我们会执着于有没有收获这件事本身呢？可能是沉没成本啊，因为我本可以选择做其他事情的。那你为何不去做呢？我不知道…一顿的跟自己较劲，左右互博，又能得出什么所以然呢？题该在哪，还是在那。不来不去，动的是我们自己本身。