描述

题目描述

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

示例

输入：
abcdefghijklmnop
abcsafjklmnopqrstuvw
输出：
jklmnop

知识点：字符串

难度：⭐⭐⭐

题解

方法一：枚举+字符串匹配

图解：

解题思路：

通过遍历短字符串的每个字符作为起点，借助左右指针不断判断最长重复子串，可以求出结果

算法流程：

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

Java 版本代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s1=sc.nextLine();
            String s2=sc.nextLine();
            longString(s1,s2);
        }
    }
    public static void longString(String s1,String s2){
        String shortStr = s1.length() < s2.length() ? s1 : s2;
        String longStr = s1.length() > s2.length() ? s1 : s2;
        int shortLen = shortStr.length();
        int longLen = longStr.length();
        int maxLen = 0, start = 0;
        for(int i = 0; i < shortLen;i++) {
            // 剪枝，子串长度已经不可能超过maxLen，退出循环
            if(shortLen - i + 1 <= maxLen) {
                break;
            }
            // 左指针j，右指针k, 右指针逐渐向左逼近
            for(int j = i, k = shortLen; k > j; k--) {
                String subStr = shortStr.substring(i, k);
                if(longStr.contains(subStr) && maxLen < subStr.length()) {
                    maxLen = subStr.length();
                    start = j;
                    // 找到就立即返回
                    break;
                } 
            }
        }
        System.out.println(shortStr.substring(start, start + maxLen));
    }
}

复杂度分析：

时间复杂度：$O(n^2(n+m))O(n^2(n+m))$，两层for循环对字符串继续遍历截取，第二层for循环里使用了String的substring是O(n)级别,contains是O(n+m)，因此总的是$O(n^2(n+m))O(n^2(n+m))$，n为较短字符串的长度

空间复杂度：$O(1)O(1)$, 只用了常数空间。

方法二：动态规划

解题思路：

通过维护状态数组，借助动态规划思想，实现状态转移过程，不断递推得到最终结果

算法流程：

• 维护动态数组dp[i][j]表示在较短字符串str1以第i个字符结尾，str2中以第j个字符结尾时的公共子串长度。
• 从左向右递推，i为短字符串str1的结尾索引，j为str2的结尾索引
• 相等则计数，并不断更新最长公共子串的长度和结尾索引

Java 版本代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s1=sc.nextLine();
            String s2=sc.nextLine();
            System.out.println(longString(s1,s2));
        }
    }
    
    // 动态规划
    public static String longString(String str1, String str2) {
        String temp = "";
        // 保证str1是较短字符串
        if (str1.length() > str2.length()) {
            temp = str1;
            str1 = str2;
            str2 = temp;
        }
        int m = str1.length() + 1;
        int n = str2.length() + 1;
        // 表示在较短字符串str1以第i个字符结尾，str2中以第j个字符结尾时的公共子串长度。
        int[][] dp = new int[m][n];
        // 匹配字符，并记录最大值的str1的结尾下标
        int max = 0;
        int index = 0;
        // 从左向右递推，i为短字符串str1的结尾索引，j为str2的结尾索引
        for (int i=1; i < m; i++) {
            for (int j=1; j < n; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    // 相等则计数
                    dp[i][j] = dp[i-1][j-1] + 1;
                    // 不断更新变量
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        index = i;
                    }
                }
            }
        }
        // 截取最大公共子串
        return str1.substring(index-max, index);
    }
}

复杂度分析：

时间复杂度：$O(mn)O(mn)$，两层for循环，需要枚举字符串的每个字符作为起点，m和n分别为两个字符串的长度

空间复杂度：$O(mn)O(mn)$, 维护了状态数组保存递推状态，n和m分别是str1和str2的长度