首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串
  • 热度指数：188847 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 

数据范围：
要求： 空间复杂度 ，时间复杂度
示例1

输入

"1AB2345CD","12345EF"

输出

"2345"

备注:
算法知识视频讲解
添加回答
推荐
bokerr头像 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)
Python
Keosu头像 Keosu 
class Solution:
    def LCS(self , str1 , str2 ):
        dp = [ [''] * (len(str2) + 1) for _ in range(len(str1) + 1)] 
        ans = ''
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                    ans = dp[i][j] if len(dp[i][j]) >= len(ans) else ans
                else:
                    dp[i][j] = ''
        return ans

发表于 2021-07-03 15:28:04 回复(0)
Python
随心！！头像 随心！！
有些通过的代码是不是有问题啊？
编辑于 2021-05-19 10:47:56 回复(0)
Python
牛客622181604号头像 牛客622181604号
#暴力法
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        max_com = 0
        str_com = ''
        for i in range(len(str1)):
            for j in range(len(str2)):
                if str1[i] == str2[j]:
                    left_eps = 1
                    right_eps = 1 
                    while i-left_eps>=0 and j-left_eps>=0 and str1[i-left_eps] == str2[j-left_eps]:
                        left_eps += 1
                    while i+right_eps<len(str1) and j+right_eps<len(str2) and str1[i+right_eps] == str2[j+right_eps]:
                        right_eps += 1
                    if left_eps+right_eps-1 > max_com:
                        max_com = left_eps+right_eps-1
                        str_com = str1[i+1-left_eps:i+right_eps]  # 注意不包含右侧
        return str_com
发表于 2021-04-04 19:33:42 回复(0)
Python
牛客378155865号头像 牛客378155865号 
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        strlen1 = len(str1)
        strlen2 = len(str2)
        record = [[0 for i in range(strlen2+1)] for j in range(strlen1+1)]
        maxnum = 0
        p = 0
        for i in range(strlen1):
            for j in range(strlen2):
                if str1[i] == str2[j]:
                    record[i+1][j+1] = record[i][j]+1
                    if record[i+1][j+1] > maxnum:
                        maxnum = record[i+1][j+1]
                        p = i +1
        return str1[p-maxnum: p]

发表于 2021-03-14 15:12:41 回复(0)
Python
牛客208065635号头像 牛客208065635号

python 答案， 时间复杂度O(n2)   简洁 优雅 易懂 


class Solution:
    def LCS(self , str1 , str2 ):
        a, b = '', ''
        for i in str1:
            a += i
            if a in str2:
                b = a
            else:
                a = a[1:]
        return b

编辑于 2021-04-26 19:39:08 回复(8)
Python
Lying1128头像 Lying1128
python3，通过所有用例。*用max记录当前找到的最长子串 
class Solution:
    def LCS(self, str1, str2):
        maxStr = str1 if len(str1) > len(str2) else str2
        minStr = str2 if len(str1) > len(str2) else str1
        Str = ""
        max = ""
        if maxStr == minStr:
            return maxStr
        for i in range(len(minStr)):
            index = maxStr.find(minStr[i])
            if index >= 0:
                s = maxStr[index:]
                s2 = minStr[i:]
                for z in range(len(s2)):
                    Str = Str + s2[z]
                    if s.find(Str) < 0:
                        break
                max = Str[:-1] if len(Str[:-1]) > len(max) else max
                Str = ""

        return max if max else 0




编辑于 2021-03-02 16:55:40 回复(0)
Python
alfred_fomo头像 alfred_fomo
可以参考leetcode上面的【1143. 最长公共子序列】
区别在于1143这道题是求【最长公共子序列】的数目，本题要求是求【最长公共子串】，区别在于前者的子序列指的是【原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串】，本题的【最长公共子串】中的子串指的是连续子序列。
以下代码是1143这道题的解法： 
def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        m=len(text1)
        n=len(text2)
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]
本题区别在于如果 str1[i-1] != str2[j-1]说明不是连续的子串，那么不做处理，只处理str1[i-1] == str2[j-1]的情况，使用maxlen记录最长的连续子串的长度，index记录最长连续子串末尾的序号。 
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        m=len(str1)
        n=len(str2)
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        maxlen = 0
        index = 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 maxlen<dp[i][j]:
                        maxlen=dp[i][j]
                        index=i
        if maxlen==0:
            return ''
        else:
            return str1[index-maxlen:index]


编辑于 2021-02-27 01:46:25 回复(1)
Python
穿过那层云，便是山顶头像 穿过那层云，便是山顶
这系统有bug，最优解刷不过，在其他编辑器上能过
发表于 2021-01-06 11:36:18 回复(1)
提交观点

问题信息

动态规划
难度：
9条回答 12879浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号