最长公共子串_

推荐

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)

Java

惠灵顿靖

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        int maxnum=0;
        int finish=0;
        int [][] dp=new int[str1.length()][str2.length()];
        for(int i=0;i<str1.length();i++)
        {
            for(int j=0;j<str2.length();j++)
            {
                if(str1.charAt(i)==str2.charAt(j))
                {
                    if(i==0||j==0)
                        dp[i][j]=1;
                    else
                        dp[i][j]=dp[i-1][j-1]+1;
                }
                if(dp[i][j]>maxnum)
                {
                    maxnum=dp[i][j];
                    finish=i;
                }
            }
        }
        if(maxnum==0)return "-1";
        return str1.substring(finish+1-maxnum,finish+1);
    }
}

详细讲解：https://www.bilibili.com/video/BV1hv41117gC?from=search&seid=4120496474797502551

发表于 2021-04-06 21:23:43 回复(0)

C/C++

BrainerGao

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
char* LCS(char* str1, char* str2 ) {
    int m = strlen(str1);
    int n = strlen(str2);
    int start = 0;
    int maxLen = 0;
    int k = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (str1[i + k] == str2[j]) {
                k++;
                if (maxLen < k) {
                    maxLen = k;
                    start = i;
                }
            } else {
                j -= k;
                k = 0;
            }
        }
    }
    str1[start + maxLen] = '\0';
    return str1 + start;
}

发表于 2021-02-28 18:15:05 回复(1)

MyBody

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串

*/

//参考题解的java，修改了一下。因为太少讨论特别是ts的，就发一版记录一下

export function LCS(str1: string, str2: string): string {
// write code here

let maxLenth = 0;//记录最长公共子串的长度
//记录最长公共子串最后一个元素在字符串str1中的位置
let maxLastIndex = 0;
let dp:Array<any> = [];
for(var t:number = 0; t< Math.max(str1.length,str2.length);t++){
dp.push(0)
}
for (let i = 0; i < str1.length; i++) {
//注意这里是倒叙
for (let j = str2.length - 1; j >= 0; j--) {
//递推公式，两个字符相等的情况
if (str1.charAt(i) == str2.charAt(j)) {
dp[j + 1] = dp[j] + 1;
//如果遇到了更长的子串，要更新，记录最长子串的长度，
//以及最长子串最后一个元素的位置
if (dp[j + 1] > maxLenth) {
maxLenth = dp[j + 1];
maxLastIndex = i;
}
} else {
//递推公式，两个字符不相等的情况
dp[j + 1] = 0;
}
}
}
//最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
}

发表于 2021-12-15 21:49:40 回复(0)

想润的我反对画饼

public class Solution {
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// write code here
int maxlength = 0;
int maxIndex = 0;
int wideth = str2.length();
int [] dp = new int[wideth+1];
for(int i = 0;i<str1.length();i++){
for(int j = str2.length()-1;j>=0;j--){
if(str1.charAt(i) == str2.charAt(j)){
dp[j+1] = dp[j]+1;
if(dp[j+1] > maxlength){
maxlength = dp[j+1];
maxIndex = i;
}
}
else{
dp[j] = 0;
}
}
}
return str1.substring(maxIndex-maxlength+1,maxIndex+1);
}
}

发表于 2021-12-03 16:56:08 回复(1)

C++

等一个广哥哥

class Solution {
public:
string LCS(string str1, string str2) {
int len1 = str1.size();
int len2 = str2.size();
int maxlen = 0,start = 0;
vector<vector<int>> dp(len1 + 1,vector<int>(len2 + 1,0));
for(int i = 1;i <= len1;i++)
{
for(int j = 1;j <= len2;j++)
{
if(str1[i - 1] == str2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if(dp[i][j] > maxlen)
{
maxlen = dp[i][j];
start = i;
}
}
}
return str1.substr(start - maxlen,maxlen);
}
};

发表于 2021-08-20 21:44:03 回复(0)

还没有上岸的菜鸡

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        return process(str1,str2);
    }
    public static String process(String str1,String str2){
        int p1 = str1.length()-1;
        int p2 = str2.length()-1;
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
        int[][] dp = new int[p2+1][p1+1];
        int max = 0;
        int pmax = -1;
        for (int i = p2; i >= 0 ; i--){
            for (int j = p1; j >= 0 ; j--){
                if(cs1[j] == cs2[i]){
                    int count = 0;
                    if (j+1 <= p1 && i+1 <= p2){
                       count = dp[i+1][j+1];
                    }
                    dp[i][j] = count+1;
                    if (dp[i][j] >= max ){
                        max = dp[i][j];
                        pmax = j;
                    }
                }
            }
        }
        StringBuilder stringBuilder = new StringBuilder("");
        for (int i = 0; i < max ; i++){
            stringBuilder.append(cs1[pmax++]);
        }
        return stringBuilder.toString();
    }
}

发表于 2021-05-18 16:36:22 回复(0)

Java

混子炒番茄

JAVA实现,动态规划方法，优化一下空间复杂度。

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if(str1 == null || str2 == null) return null;
//         char[] s1 = str1.toCharArray();
//         char[] s2 = str2.toCharArray();
//         int[][] dp = new int[str1.length()][str2.length()];
//         int r = 0,c = 0;
//         //循环中判断特殊情况
//         for(int i=0;i<s1.length;i++) {
//             for(int j=0;j<s2.length;j++) {
//                 if(s1[i]==s2[j]) {
//                    dp[i][j] = (i==0||j==0) ? 1 : dp[i-1][j-1]+1;
//                 }else {
//                    dp[i][j] = 0;
//                 }
//                 if(dp[i][j] > dp[r][c]) {
//                     r=i;
//                     c=j;
//                 }
//             }
//         }
        
        //先将特殊情况在循环外赋值，少一次判断时间；
//         for(int i = 0;i<s1.length;i++) {
//             dp[i][0] = s1[i]==s2[0] ? 1 : 0;
//         }
//         for(int j = 0;j<s2.length;j++) {
//             dp[0][j]= s1[0]==s2[j] ? 1 : 0;
//         }
//         for(int i=1;i<s1.length;i++) {
//             for(int j=1;j<s2.length;j++) {
//                 dp[i][j] = s1[i]==s2[j] ? dp[i-1][j-1]+1 : 0;
//                 if(dp[i][j] > dp[r][c]) {
//                     r=i;
//                     c=j;
//                 }
//             }
//         }        
//        return str1.substring(r-dp[r][c]+1,r+1);
        //节省空间，每一次的计算只需要上一层的数据，每一格的计算只需要左上角的数据，从右向左计算即可
        //固定s1为较长的字符串，s2为较短的字符串
        //较短字符串长度的空间
        char[] s1,s2;
        if(str1.length() < str2.length()) {
           s1 = str2.toCharArray();
           s2 = str1.toCharArray();
        }else{
            s1 = str1.toCharArray();
            s2 = str2.toCharArray();
        }
        int[] dp = new int[s2.length];
        int flag =0;//记录当前最长公共子串长度；
        int index = -1;//记录最长公共子串在较长字符串中的结束下标；
        for(int i=0;i<dp.length;i++)
            dp[i] = s1[0]==s2[i] ? 1 : 0;
        for(int i=1;i<s1.length;i++) {
            for(int j=s2.length-1;j>0;j--) {
                dp[j] = s1[i]==s2[j] ? dp[j-1]+1 : 0;
                if(dp[j] > flag) {
                    flag = dp[j];
                    index = i;
                }
            }
            dp[0] = s1[i]==s2[0] ? 1 : 0;  //将第0列单独处理，省去一次判断
        }
        return str1.length() < str2.length() ? str2.substring(index-flag+1,index+1) : str1.substring(index-flag+1,index+1);
    }
}

发表于 2021-04-21 19:27:57 回复(0)

Java

肥猿

解题思路：动态规划，如果当前两个字符串相等，则dp值设为一，下一对类推，反之则为0，记录下最大长度，以及位置，然后最后进行字符串截取

import java.util.*;

public class Solution {
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS (String str1, String str2) {
// write code here
if(str1 == null || str2 == null || str1.equals("") || str2.equals("")){
return "-1";
}
int indexMax = 0;
int maxLen = 0;
int m = str1.length();
int n = str2.length();

int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(str1.charAt(i)==str2.charAt(j)){
if(i==0||j==0){
dp[i][j]=1;
}else{
dp[i][j]=dp[i-1][j-1]+1;
}
}
if(maxLen<dp[i][j]){
maxLen=dp[i][j];
indexMax=i;
}
}
}
if(maxLen==0) return "-1";
return str1.substring(indexMax-maxLen+1,indexMax+1);
}
}

发表于 2021-03-13 14:00:38 回复(0)

cyysteven

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        int end = 0;
        int maxLength = 0;
        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else dp[i][j] = 0;
                if(maxLength < dp[i][j]){
                    end = i;
                    maxLength = dp[i][j];
                }
            }
        }
        return str1.substring(end-maxLength, end);
    }
}

动态数组：

f (i,j) 表示str1.charAt（i）和 str2.charAt（j）相同时，最长子串的长度；

f(i, j) = str1.charAt(i) == str2.charAt(j)? f(i-1, j-1) +1 : 0;

** dp数组多加一行一列简化数组越界问题。

编辑于 2021-03-11 00:38:36 回复(0)

佛系**

public static String LCS (String str1, String str2) {
        // write code here
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "-1";
        }
        String curStr = "";
        String maxStr = "";
        for (char c : str2.toCharArray()) {
            curStr += c;
            if (str1.contains(curStr)) {
                if (curStr.length() > maxStr.length()) {
                    maxStr = curStr;      //如果str1包含当前curStr，并且curStr的长度大于maxStr，那么用curStr替换maxStr。
                }
            } else {   //如果不包含，curStr从第一个字符递减，直到str1继续包含目前的curStr
                while(true) {
                    curStr = curStr.substring(1,curStr.length());
                    if(str1.contains(curStr)) {
                        break;
                    }
                }
            }
        }
        return maxStr;
    }

发表于 2021-03-08 17:00:03 回复(1)

Java

想踢足球的小学生在备战秋招

使用动态规划，优化前：

public static String LCS1 (String str1, String str2) {
        // write code here
        int res[][]=new int[str1.length()][str2.length()];
        int min=0,maxLen=0;
        for(int i=0;i<str1.length();i++){
            if(str1.charAt(i)==str2.charAt(0)){
                res[i][0]=1;
            }else{
                res[i][0]=0;
            }
        }
        for(int i=0;i<str2.length();i++){
            if(str2.charAt(i)==str1.charAt(0)){
                res[0][i]=1;
            }else{
                res[0][i]=0;
            }
        }

        for(int i=1;i<str1.length();i++){
            for(int j=1;j<str2.length();j++){
                if(str1.charAt(i)==str2.charAt(j)){
                    res[i][j]=res[i-1][j-1]+1;
                    if(maxLen<res[i][j]){
                        maxLen=res[i][j];
                        min=i;
                    }

                }
            }
        }
        return maxLen==0?"-1":str1.substring(min-maxLen+1,min+1);
    }

优化后：

  public static String LCS (String str1, String str2) {
        // write code here
        if(str1==null||str2==null||str1.length()==0||str2.length()==0){
            return "-1";
        }
        int end=0;
        int maxLen=0;
        int dp[][]=new int[str1.length()+1][str2.length()+1];
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if(str2.charAt(j)==str1.charAt(i)){
                    if(i==0||j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                    if(dp[i][j]>maxLen){
                        maxLen=dp[i][j];
                        end = i;
                    }
                }
            }
        }
       return maxLen==0?"-1":str1.substring(end-maxLen+1,end+1);
    }

发表于 2021-01-02 14:08:30 回复(1)

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)

大鹏呀

个人实在不理解通过的python代码，很明显存在漏洞，但不知道为什么编译讷讷通过，只要公共字符串不是以其中的一个字符串开头，编译无法通过
个人认为下面才是正确的

class Solution:
    def LCS(self,str1 , str2 ):
        # write code here
        if len(str1) < len(str2):
            str1, str2 = str2, str1
        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

发表于 2021-04-07 09:44:18 回复(8)

Java

matrixZ

动态规划最优解：

由于dp table关系不是连续的，需要用max记录连续最大值

index记录max最大时候的坐标，用于确定子串

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        int max = 0, index = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (max < dp[i + 1][j + 1]) {
                        max = dp[i + 1][j + 1];
                        index = i + 1;
                    }
                }
            }
        }
        return max == 0 ? "-1" : str1.substring(index-max,index);
    }
}

编辑于 2021-01-31 18:06:04 回复(12)

STAY201909201320835

public String LCS (String str1, String str2) {
        // Invariant
        // lcs[i][j] 代表以str1[i]，str2[j]结尾的最长公共子串
        // i，j 从1开始
        int[][] lcs = new int[str1.length() + 1][str2.length() + 1];

        int max = 0;
        // str1的下标
        int index = 0;
        for (int i = 1; i <= str1.length(); i++)
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                    if (lcs[i][j] > max) {
                        max = lcs[i][j];
                        index = i;
                    }
                }
            }

        return str1.substring(index - max, index);
    }

发表于 2021-03-10 14:08:16 回复(1)

C++

牛客782540893号

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        //string res;
        int start=0;
        int i=1;
        string res;
        //设置一个小窗，start是开始坐标，i是小窗长度，且i只会增大不会减小。
        while(start<str2.size() && start+i <= str2.size()){
            string temp(str2,start,i);  //将str2以start开始的i个字符用于构造temp
            if(str1.find(temp) != -1){
                i++;
                res=temp;  //如果在str1中找到了小窗内的子串，就把小窗增大
            }
            else{
                start++;  //如果找不到子串，就将小窗向右移动一格。
            }
        }
        return res;
    }
};

C++

发表于 2021-07-29 15:23:22 回复(0)

Python

牛客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)

古希腊掌管八股之神

Longest Common SubString最长公共子串 - 结果

Longest Common SubSequece最长公共子序列 - 结果

Longest Increasing SubSequence最长递增子序列 - 长度 & 结果

无重复字符的最长子串 - 长度

拿下可能要一年（对我来说）

发表于 2020-10-27 15:38:41 回复(9)

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)

C++

外天楼

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        //+1为了方便计算 [0-1] 的情况
        vector<vector<int>> dpVec(str1.size()+1, vector<int>(str2.size()+1, 0));
        // 012345678
        //"1AB2345CD",
        //"  12345EF"
        //endIndex = 6, len = 4
        //i1,i2取dpVec位置，取字符时需要-1
        int maxLen = 0;
        vector<int> maxEndIndex{0,0};
        for (int i1 = 1; i1 <= str1.size(); i1++) {
            for (int i2 = 1; i2 <= str2.size(); i2++) {
                //如果当前位置的字符相等，那么最长公共子串就等于都减去这个字符后的最长长度在+1
                if (str1[i1-1] == str2[i2-1]) {
                    dpVec[i1][i2] = dpVec[i1-1][i2-1] + 1;
                    if (dpVec[i1][i2] > maxLen) {
                        maxLen = dpVec[i1][i2];
                        maxEndIndex = {i1-1,i2-1};
                    }
                } else {
                    dpVec[i1][i2] = 0;
                }
            }
        }
        return str1.substr(maxEndIndex[0] - maxLen + 1, maxLen);
    }
};

发表于 2021-09-22 14:50:18 回复(0)

最长公共子串

输入

输出

备注:

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

问题信息

热门推荐

通过挑战的用户

相关试题

最长公共子串

输入

输出

备注:

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

问题信息

热门推荐

通过挑战的用户

相关试题

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