我要招人

去企业版

首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串

热度指数：198753 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： $1 \le |str1|,|str2| \le 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1

输入

"1AB2345CD","12345EF"

输出

"2345"

备注:

算法知识视频讲解

推荐

bokerr

如图，自左上->右下的对折线上最长连续交点即为最大字串，为了节省内存开销我没使用二维数组，直接通过记录步长处理的，并在适当位置判断能否提前推出计算，最极限情况，0(2n) 即可退出(str2是str1子串)；反之则需要遍历，O(n*m)(最长字串只有一个字符)；

思路其实非常简单，代码看起来方法挺多只是我稍微封装了一下，为了看起来简洁；实际上这种程度的封装，在编译器优化时可以相当轻松的完成方法内联。(评论区贴的不一定是对的，我从评论区拷了很多个拿来测试都是过不了的，一度让我怀疑题目有bug，干了一些蠢事(羞耻到打滚))。

import java.util.*;
public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    //状态记录，取缔二维数组，减少内存开销
    int start = 0;
    int stepNum = 0;
    int currentStart = 0;
    int currentStepNum = 0;
    boolean cancleLeft = false;
    boolean cancleRight = false;
    int len2 = 0;
    public String LCS (String str1, String str2) {
        String breakJudge;
        if (str1.length() < str2.length()){
            String temp = str1; str1 = str2; str2 = temp;
        }
        len2 = str2.length();
        for (int i = 0;i < str1.length() && !cancleRight;i++){
            for (int j = 0; j < str2.length() && i + j < str1.length();j++)
                doJudge(str1,str2,j + i,j);
            clear();
            if (!cancleRight)
                cancleRight = breakJudge(str1.length(),i);
        }
        clear();
        for (int i = 0;i < str2.length() && ! cancleLeft;i++){
            for (int j = 0; i + j < str2.length();j++)
                doJudge(str1,str2,j,j + i);
            clear();
            if (!cancleLeft)
                cancleLeft = breakJudge(str2.length(),i);
        }
        return stepNum == 0 ? "-1" : str1.substring(start,start + stepNum);
    }
    // 判断能否提前退出
    public boolean breakJudge(int len,int i){
        if (stepNum == len2 || (stepNum >= (len - i))){
            return true;
        }
        return false;
    }

    public void clear(){
        if (currentStepNum > stepNum){
            stepNum = currentStepNum;
            start = currentStart;
        }
        currentStepNum = 0;
        currentStart = 0;
    }
    public void doJudge(String str1,String str2,int index1,int index2){
        if ( str1.charAt(index1) == str2.charAt(index2)){
            if (currentStepNum == 0)// 记录步长为0
                currentStart = index1; //更新起点
            currentStepNum ++;//步长加一
        } else
            clear();//不等，对比当前步长与缓存步长,更新保存的步长与起点
    }
}

编辑于 2021-07-06 10:32:40 回复(1)

Python3

在喝茶的小鱼干很苦闷

class Solution:
    def LCS3(self, str1: str, str2: str):
        m, n = len(str1), len(str2)
        top, digit =min(m, n), 0
        while top//(10**digit)>10:
            digit += 1
        while digit>=0:
            longest, index = 0, 0
            for length in range(top, 0, -10**digit):
                for i in range(m - length + 1):
                    if str1[i:i+length] in str2:
                        longest = length
                        index = i
                        break
                if longest: break
            top = length+10**digit
            digit -= 1

        return str1[index:index + longest]

发表于 2024-07-12 20:28:56 回复(0)

Python3

青霄霄

为什么python的动态规划会超时呢？

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here

        m = len(str1)
        n = len(str2)
        d = [[0]*n for _ in range(m)]
        for j in range(n):
            d[0][j] = 1 if str1[0] == str2[j] else 0
        for i in range(m):
            d[i][0] = 1 if str1[i] == str2[0] else 0
        
        maxij = [0,0,0]
        for i in range(1,m):
            for j in range(1,n):
                if str1[i] == str2[j]:
                    d[i][j] = 1+ d[i-1][j-1]
                    if d[i][j] > maxij[0]:
                        maxij = [d[i][j],i,j]

        return str1[1+maxij[1]-maxij[0]:1+maxij[1]]

编辑于 2024-02-29 17:36:12 回复(1)

Python3

已注销

为啥超时啊

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        end_index, max_length = 0, 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1

                    if dp[i][j] > max_length:
                        max_length = dp[i][j]
                        end_index = i
        
        return str1[end_index - max_length:end_index]

发表于 2023-09-12 16:26:32 回复(0)

Python3

Vivimore

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        res = ''
        max_len = 0
        for i in range(len(str1)):
            if str1[i - max_len:i+1] in str2:
                res = str1[i - max_len:i+1]
                max_len += 1
        return res

发表于 2022-05-21 14:28:06 回复(4)

Python3

tangjunjun

class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        maxLen = 0
        endIndex = 0
        
        f = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]
        
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if (str1[i-1] == str2[j-1]):
                    f[i][j] = f[i-1][j-1] + 1
                else:
                    f[i][j] = 0
                if maxLen < f[i][j]:
                    maxLen = f[i][j]
                    endIndex = i # end index of the first string
        
        # print(maxLen)
        return str1[endIndex-maxLen:endIndex]
        
        
        
#         if len(str1) < len(str2):
#             str1, str2 = str2, str1
#         res = ''
#         maxLen = 0
#         for i in range(len(str1)):
#             if str1[i - maxLen: i+1] in str2:
#                 res = str1[i-maxLen:i+1]
#                 maxLen += 1  # 继续在原来长度上前行
#         if len(res) == 0:
#             return -1
#         return res

发表于 2021-11-16 22:31:18 回复(2)

Python3

又要找工作了

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        if len(str1) < len(str2):
            str1, str2 = str2, str1
        res = ''
        maxLen = 0
        for i in range(len(str1)):
            if str1[i - maxLen: i+1] in str2:
                res = str1[i-maxLen:i+1]
                maxLen += 1
        if len(res) == 0:
            return -1
        return res

发表于 2021-10-28 21:12:46 回复(4)