Java题解|65 #查找两个字符串a,b中的最长公共子串#

描述

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

数据范围：字符串长度 1≤length≤300

进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)

输入描述：
输入两个字符串

输出描述：
返回重复出现的字符

示例1

输入：
abcdefghijklmnop
abcsafjklmnopqrstuvw

输出：
jklmnop

解法

注意几个关键字

• “最长”公共子串
• “较短”串中“最先”出现

因此，

• 从较短的那条输入字符串作为遍历基础。假设两个字符串a为较短,b为较长。
• 假设a的长度为aLength，从a截取长度为aSubLength的子串，开始截取位置为0。aSubLength初始长度为aLength。
• 看a截取子串在b中是否包含。
  • 如果包含，则程序结束，此时的a截取子串即为“最长”、“最先”公共子串；
  • 否则，尝试从a截取子串，开始截取位置为0，aSubLength初始长度为aLength-1。
  • 如果还不包含，则继续尝试从a截取子串，开始截取位置为1，aSubLength初始长度为aLength-1。

/**
 * Welcome to https://waylau.com
 */
package com.waylau.nowcoder.exam.oj.huawei;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * HJ65 查找两个字符串a,b中的最长公共子串.
 * 描述:查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 * 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。
 * 请和“子序列”的概念分开！
 * 数据范围：字符串长度 1≤length≤300
 * 进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)
 * 输入描述：
 * 输入两个字符串
 * 输出描述：
 * 返回重复出现的字符
 * 示例1
 * 输入：
 * abcdefghijklmnop
 * abcsafjklmnopqrstuvw
 * 输出：
 * jklmnop
 * 
 * @since 1.0.0 2022年8月27日
 * @author <a href="https://waylau.com">Way Lau</a>
 */
public class HJ065FindLongestCommonSubstringInTwoStrings {
    public static void main(String[] args)
            throws IOException {
        // 输入
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();

        // a作为较短的那个字符串
        String a;
        String b;
        if (str1.length() <= str2.length()) {
            a = str1;
            b = str2;
        } else {
            a = str2;
            b = str1;
        }

        // 看a截取子串在b中是否包含
        int aLength = a.length();
        int aSubLength = aLength;
        String result = "";
        boolean isContinue = true;
        while (aSubLength > 0 && isContinue) {
            // 从前往后截取
            for (int i = 0; i < aLength - aSubLength + 1; i++) {
                String aSub = a.substring(i,
                        i + aSubLength);

                // 如果包含，则程序结束
                if (b.contains(aSub)) {
                    result = aSub;
                    isContinue = false;
                    break;
                }

            }

            // 缩小截取的范围
            aSubLength--;
        }

        // 输出
        System.out.println(result);

        // 关闭
        br.close();
    }

}

参考引用

• 本系列归档至https://github.com/waylau/nowcoder-exam-oj
• 《Java 数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action
• 《数据结构和算法基础（Java 语言实现）》（柳伟卫著，北京大学出版社出版）：https://item.jd.com/13014179.html