首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串

热度指数：12901 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。

给定两个字符串A和B，同时给定两串的长度n和m。

测试样例：

"1AB2345CD",9,"12345EF",7

返回：4

算法知识视频讲解

推荐

还有多远

注意，这里要求的是最长公共子字符串（要求连续），而不是最长公共子串（不一定连续）

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        //f[i][j] represent the longest common substring starting with A[i] and B[j]
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));
        //maxlen is the overall max common substring length, starting anywhere
        int maxlen = 0;
        //dp
        for(int i = n-1; i > -1; --i){
            for(int j = m-1; j > -1; --j){
                if(A[i] != B[j]){
                    //no such common substring started with A[i] and B[j]
                    //f[i][j] remain 0 as initialized
                }
                else{
                    //common substring starts with A[i] and B[j]
                    f[i][j] = f[i+1][j+1] + 1;
                    maxlen = max(maxlen, f[i][j]);
                }
            }
        }
        return maxlen;
    }
};

编辑于 2015-08-18 09:55:14 回复(6)

一枚水货

//经典动态规划问题，所以使用动态规划更方便一些吧
public int findLongest(String A, int n, String B, int m) {
        char[] arrA=A.toCharArray();
		char[] arrB=B.toCharArray();
		int[][] dp=new int[n][m];
		int max=0;
		for(int i=0;i<n;i++){
			if(arrA[i]==arrB[0])
				dp[i][0]=1;
		}
		for(int j=1;j<m;j++){
			if(arrB[j]==arrA[0])
				dp[0][j]=1;
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<m;j++){
				if(arrA[i]==arrB[j])
					max=Math.max(dp[i][j]=dp[i-1][j-1]+1, max);
			}
		}
		return max;
    }

发表于 2016-08-01 20:09:30 回复(4)

夕一啊

用这个来表示连续也是醉了，误导我，还以为一定是递增序列呢。。。

看懂了披萨大叔的答案，

这道题和算法书上的动态规划最长子序列的差别就在于这个必须连续，所以在更新矩阵的时候，如果此刻比较的ij位值不等，不会取左边或者上面的值，只有在连续相等的时候取左上角一位加一

（借用下披萨大叔的图）

发表于 2017-06-28 17:23:29 回复(1)

Python

TimeMac

动态规划问题

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        if n > m:
            A,B,n,m = B,A,m,n
        result = [[0 for i in range(m)] for j in range(n)]  
        #result[i][j]表示子串A前i个和子串B前j个的最大公共子串
        numMax = 0
        for i in range(n):
            for j in range(m):
                if A[i]==B[j]:
                    if i>0 and j>0:  #第一个字符相等初始化为1，否则左上角加一
                        result[i][j] = result[i-1][j-1]+1
                    else:
                        result[i][j] = 1
                    if numMax<result[i][j]:
                        numMax = result[i][j]
        return numMax

编辑于 2018-09-23 17:59:57 回复(0)

Java

龙虾姐夫

结果对了，两个for循环时间复杂度好像不满足要求
import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        
        int max=0;

            for(int i=0;i<m;i++)
            {
                int temp=0;
                for(int j=i+1;j<m+1;j++)
                {                    
                    String subStr=B.substring(i,j);
                	if(A.contains(subStr))
                    {
                        temp=j-i;
                        
                    }
                    else{                                                
                        break;
                    }                    
                }
                if(max<temp)
                {
                    max=temp;                   
                }         
            }
        
        return max;
               
    }
}

编辑于 2016-07-08 15:18:51 回复(0)

jo_ryan

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        // write code here
    int i,j;
    if (0 == m || 0 == n)
        {
            return 0;
        }
/*************getdp[][]******************/
    int dp[m][n];
    for (i = 0; i < m; i++)
    {
        if (B[i] == A[0])
        {
            dp[i][0] = 1;
        }
        else
            dp[i][0] = 0;
    }
    for (j = 1; j < n; j++)
    {
        if (B[0] == A[j])
        {
            dp[0][j] = 1;
        }
        else
            dp[0][j] = 0;
    }
    for (i = 1; i < m; i++)
    {
        for (j = 1; j < n; j++)
        {
            if (B[i] == A[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
                dp[i][j] = 0;
        }
    }
    int max = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (dp[i][j] > max) {
                max = dp[i][j];
            }
        }
    }
    return  max;
    }
};

发表于 2015-08-22 15:11:18 回复(0)

Java

可以0613

import java.util.*;

public class LongestSubstring {
public int findLongest(String A, int n, String B, int m) {
if (A == null || B == null) {
return -1;
}
int[][] dp = new int[n + 1][m + 1];
int lmax = 0; //因为是连续的，所以不一定dp数组中最后一个就是最大的，所以用lmax来记录
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if(dp[i][j] > lmax)
{
lmax = dp[i][j];
}
}
}
}
return lmax;
}
}

发表于 2020-03-26 21:47:32 回复(0)

张永胜潮阳

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        int[][] dp = new int[n+1][m+1];
        int res = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(A.charAt(i)==B.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]>0?dp[i][j]+1:1;
                    res = Math.max(res,dp[i+1][j+1]);
                }
            }
        }
        return res;
    }
}

编辑于 2019-01-18 20:54:04 回复(0)

杰斯007

DP解法：时间空间复杂度都为log(m*n)
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {

        if (n == 0 || m == 0) return 0;
        return getdp(A,n,B,m);
        //如果返回公共最长字符串则：
        //int max=0;int end = 0;
        //for (int i = 0; i<n; i++)
        //{
        //    for (int j = 0; j<m; j++){
        //        if (dp[i][j]>max)
        //        {
        //            max = dp[i][j];end=i;
        //        }
        //    }
        //}
        //return A.sub(end-max+1,max);
    }
    int getdp(string arrA, int n, string arrB, int m)
    {
        int res=0;
        vector<vector<int> >dp(n, vector<int>(m, 0));
        for (int i = 0; i<n; i++){
            if (arrA[i] == arrB[0])
                dp[i][0] = 1;
        }
        for (int j = 1; j<m; j++){
            if (arrB[j] == arrA[0])
                dp[0][j] = 1;
        }
        for (int i = 1; i<n; i++){
            for (int j = 1; j<m; j++){
                if (arrA[i] == arrB[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = max(dp[i][j], res);
            }
        }
        return res;
    }
};

暴力解法：
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        // write code here
        if (n == 0 || m == 0) return 0;
        int res = 0, max = 0;
        for (int i = 0; i<n; i++)
        {
            for (int j = 0; j<m; j++){
                int tmpi = i;
                int tmpj = j;
                while (tmpi<n&&tmpj<m&&A[tmpi] == B[tmpj])
                {
                    res++; tmpi++; tmpj++;
                }
                if (res>max)
                {
                    max = res;
                }
                res = 0;
                
            }
        }
        return max;
    }
};

编辑于 2018-04-07 15:44:56 回复(0)

yiixuu

import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        int[] record = new int[n];
        int maxLength = 0;
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                
                if (A.charAt(j) == B.charAt(i)) {
                    if (j == 0) {
                        record[j] = 1;
                    } else {
                        record[j] = record[j-1] + 1;
                    }
                    maxLength = Math.max(record[j], maxLength);
                    
                } else {
                    record[j] = 0;
                }
            }
        }
        return maxLength;
    }
}

补充【优化】，使用一维数组记录相同子串长度并不断更新。

编辑于 2018-02-21 16:01:30 回复(0)

Miyagi11

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int dp[1000][1000];
        string new_a="#"+A;
        string new_b="#"+B;
        for(int i=0;i<=n;i++) dp[0][i]=0;
        for(int i=0;i<=m;i++) dp[i][0]=0;
        int max=-99;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(new_a[i]==new_b[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>max) max=dp[i][j];
                }
                else dp[i][j]=0;
            }
        }
        return max;
    }
};

发表于 2018-02-19 16:11:10 回复(0)

C/C++

nbgao

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        vector<vector<int> > dp(n+1,vector<int>(m+1,0));
        int Max = 0;         for(int i=0;i<=n;i++)
            if(A[i]==B[0])
                dp[i][0] = 1;
        for(int j=1;j<=m;j++)
            if(B[j]==A[0])
                dp[0][j]=1;
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                if(A[i]==B[j])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    Max = max(Max, dp[i][j]);                 }
                 return Max;                     }
};

发表于 2017-10-16 01:14:06 回复(0)

M00N

package dp;
/**
最长公共子串

题目描述:
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，
求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，
其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
给定两个字符串A和B，同时给定两串的长度n和m。
测试样例：
"1AB2345CD",9,"12345EF",7
返回：4
 */
public class LCSubstring {
    public int findLongest(String str1, int m, String str2, int n) {
    	
    	char[] s1 = str1.toCharArray();
    	char[] s2 = str2.toCharArray();
    	int[][] dp = new int[m+1][n+1];

    	int maxLen = 0;
    	for (int i = 1; i <= m; i++) {
    		for (int j = 1; j <= n; j++) {
    			if (s1[i-1] == s2[j-1]) {
    				dp[i][j] = dp[i-1][j-1]+1;
    				maxLen = Math.max(maxLen, dp[i][j]);
    			} else {
    				dp[i][j] = 0;
    			}
    		}
    	}
    	
    	return maxLen;
    }
}

发表于 2017-04-03 19:49:53 回复(0)

Alex-大伟

package alex.suda.dp;

import java.util.Scanner;

public class test3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			String A = scanner.next();
			int m = scanner.nextInt();
			String B = scanner.next();
			System.out.print(findLongest(A, n, B, m));
		}
	}

	public static int findLongest(String A, int n, String B, int m) {
		// d[i][j]是以A[i]和 B[j]开头的相同子串
		int[][] d = new int[n + 1][m + 1];
		// 初始化
		int maxLen = 0;
		//这种逆向的动态规划思想值得学习
		for (int i = n - 1; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				if (A.charAt(i) == B.charAt(j)) {
					d[i][j] = d[i + 1][j + 1] + 1;
					maxLen = Math.max(maxLen, d[i][j]);
				}
			}
		}
		return maxLen;

	}
}

发表于 2016-10-05 22:11:51 回复(0)

Java

不知Andy

import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        
        int p = 0,max1 = 0,count = 0,max = 0;
        for(int d = 0; d < n; d++){
            for(int i = 0; i < m; i++){
                p = (d+i)%n;
                if(p==0){
                    count = 0;                   
                }
                if(A.charAt(p)==B.charAt(i)){
                        count++;
                        max1 = Math.max(count,max1);
                }else{	
                    count = 0;
                }    
            }
            max = Math.max(max1,max);
            count=0;
        }
        return max;
    }
}

移位O(N),计数O(m);

发表于 2016-08-25 10:21:17 回复(0)

fight灬奋斗

//非动态规划，时间复杂度o(m*n),空间复杂度o(1);
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int R=0,max;
        for(int i=0;i<n;i++){
            max=0;
            for(int j=0;j<m;j++){
                if(i+j<n&&A[i+j]==B[j]){
                    max++;
                    if(max>R)
                        R=max;
                }else{
                    max=0;
                }
            }
        }
        for(int i=0;i<m;i++){
            max=0;
            for(int j=0;j<n;j++){
                if(i+j<m&&B[i+j]==A[j]){
                    max++;
                    if(max>R)
                        R=max;
                }else{
                    max=0;
                }
            }
        }
        return R;      
    }
};

编辑于 2016-08-05 08:37:34 回复(0)

尼见

时间复杂度是o(n^2)，方法比较笨，就是采用的依次遍历，从头到尾，
让两次字符串的字串去依次比较，最后得出结果 public class LongestSubstring {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new LongestSubstring().findLongest("bcbab",5,"abbabccc",8);
	}

	public int findLongest(String A, int n, String B, int m) {
		// write code here
		int sum = 0;
		int temp = 0;
		int flag = 0;
		int beginJ = 0;

		for (int i = 0; i < n; i++) {
			int beginI = i;
			for (int j = 0; j < m; j++) {
				if (flag == 0) {
					beginJ = j;
					flag = 1;
				}
				if (i < n && j < m && A.charAt(i) == B.charAt(j)) {
					i++;
					temp++;
				} else if (i < n && j < m && A.charAt(i) != B.charAt(j)) {
					flag = 0;
					temp = 0;
					i = beginI;
					j = beginJ;
				}
				if (sum < temp) {
					sum = temp;
				}
				if (j == m - 1) {
					flag = 0;
					i = beginI;
					temp = 0;
				}
			}
		}
		System.out.println(sum);
		return sum;
	}
}

发表于 2016-05-18 20:11:57 回复(0)

gloomy

import java.util.*;

public class LongestSubstring {

public int findLongest(String A, int n, String B, int m) {

return getLongestCommonSub(A,B).length();

}

public String getLongestCommonSub(String A,String B){

int a_len = A.length();

int b_len = B.length();

int[][] dp = new int[a_len][b_len];

int length = 0;

int end = 0;

for(int i = 0;i<a_len;i++){

for(int j = 0;j<b_len;j++){

if(A.charAt(i)==B.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]>length){

length = dp[i][j];

end = i;

}

return A.substring(end-length+1,end+1);

}

发表于 2016-04-06 19:32:58 回复(0)

披萨大叔

首先，所求是最大子串，不是子序列，说明是连续的。

LS问题，用动态规划思想，把大问题分解成若干小问题，用矩阵记录状态结果：

若s是两个字符串s1和s2敏感词有的字符，s1中s左侧的字符串为s1'，s2中s左侧的字符串为s2'，那么截止到s为止，LS(s1, s2) = LS(s1', s2')+1，用矩阵记录结果，例如bab和c aba，矩阵如下：

我们用全局变量max记录最大值，同时可以记录最后一次+1时的行号或列号，结合max可以推算出子串。

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        if(n == 0 || m == 0){
            return 0;
        }
        //初始化状态矩阵
        int[][] matrix = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                matrix[i][j] = 0;
            }
        }
        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(A.charAt(i) == B.charAt(j)){
                    if(i == 0 || j == 0){
                        matrix[i][j] = 1;
                    }else{
                        matrix[i][j] = matrix[i-1][j-1] + 1;
                    }
                    max = (max > matrix[i][j] ? max : matrix[i][j]);
                }
            }
        }
        return max;
    }
}

编辑于 2016-08-19 16:15:48 回复(3)

周星星_

补充一下披萨大叔的思路。

题目要求公共子串的元素必须相邻， dp矩阵是按照这样的思路想出来的：

首先：

用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.

下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。

优化：

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

ref：

http://www.cnblogs.com/dartagnan/archive/2011/10/06/2199764.html

编辑于 2016-12-11 16:52:28 回复(4)

我就信ycy拿到offer就喝一鸣

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        char[] Ac = A.toCharArray();
        char[] Bc = B.toCharArray();
                 int res = 0;                                             
        //既然每一个dp[i][j]的值的确定只是有关于斜上方的，那么就可以将dp的空间复杂度完全降低到o(1)
        // 遍历dp[][] 的另外一种方式，斜着打印
        for(int i = Bc.length-1; i >= 0; --i){
            // first ,init the first prepare value
            int curV = Ac[0] == Bc[i] ? 1 : 0;
            for(int j = i+1,k = 1; (k < Ac.length && j < Bc.length); ++j, ++k){
                curV = Ac[k] == Bc[j] ? curV+1 : 0;
                res = Math.max(res, curV);
            }
        }
        for(int i = 1; i < Ac.length; ++i){
            int curV = Bc[0] == Ac[i] ? 1 : 0;
            for(int j = i+1, k = 1; (k < Bc.length && j < Ac.length); ++j, ++k){
                curV = Ac[j] == Bc[k] ? curV+1 : 0;
                res = Math.max(res, curV);
            }
        }
        return res;
    }
}

其实最开始的思路肯定还是dp[][]数组的判断的，也就是一定要注意规定好dp[i][j]的定义，也就是他被更新的来源，表示的是以i和j位置上的字符为结尾的公共字串的最大长度，只有这样才能利用dp的中的前面求得值进行更新，也就是dp[i-1][j-1]的值+1，如果不是这个以i和j位置上的字符为结尾的公共字串的最大长度条件的话，更新的值就会有错，然后优化的话就是，你再更新的时候发现这个dp[i][j]的值只和一个值相关，那就完全可以用一个变量搞定，转而变成了一个矩阵的斜着遍历的方式

发表于 2018-04-02 16:44:11 回复(0)