【Java编程题】最大公共子串

ゝ一纸荒年。 2022-12-07 12:19 161阅读 0赞

**题目来源：**[https://www.nowcoder.com/questionTerminal/e947e4801fc64808b2390c1cf2754906][https_www.nowcoder.com_questionTerminal_e947e4801fc64808b2390c1cf2754906]

**题目描述：**给定两个字符串，请编写代码，输出最长公共子串（Longest Common Substring），是指两个字符串中的最长的公共子串，要求子串一定是连续。

**输入描述：**文本格式，2个非空字符串（字符数字组成），2个字符串以“,”英文逗号分隔，字符串长度均小于等于100；

**输出描述：**整形，为匹配到的最长子串长度；

**示例1：**

输出：bab,caba

输出：2

**方法：**找出两个字符串中较长的那个和较短的那个，然后，设置前后指针，遍历较短的字符串，再到长的字符串里面去寻找有没有这个子字符串；

**代码：**

import java.util.*;
    public class Main{
        public static void main(String [] args){
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine();
            String [] strs = str.split(",");
            System.out.println(result(strs[0] , strs[1]));
            
        }
        public static int result(String strOne, String strTwo){
            if(strOne == null || strTwo == null){
                return 0;
            }
            String max = null;
            String min = null;
             if(strOne.length() < strTwo.length()){
                min = strOne;
                max = strTwo;
            }else{
                min = strTwo;
                max = strOne;
            }
            String res = null;
            for(int i = 0; i < min.length(); i++){
                for(int start = 0, end = min.length() - i; end <= min.length(); start++, end++){
                    res = min.substring(start, end);
                    if(max.contains(res)){
                        return end - start;
                    }
                }
                
            }
            return 0;
        }
    }

其实，最经典的做法还是动态规划，但是我现在还没搞懂它（沮丧aaaaa）

[https_www.nowcoder.com_questionTerminal_e947e4801fc64808b2390c1cf2754906]: https://www.nowcoder.com/questionTerminal/e947e4801fc64808b2390c1cf2754906