首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串
  • 热度指数:12472 时间限制: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。

给定两个字符串AB,同时给定两串的长度nm

测试样例:
"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)

动态规划问题

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)
结果对了,两个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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
//非动态规划,时间复杂度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)

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)
class LongestSubstring {
 public:
     int findLongest(string A, int n, string B, int m) {
         int max=0;
         for(int i=0;i<n;i++){
             int len=0;
             for(int j=0;j<m;j++)
                 if(A[i]==B[j]){
                     len = 0;
                     while(A[i+len]==B[j+len]&&i+len<n&&j+len<m)
                         len++;
                     if(len>max) max=len;
                 }
         }
         return max;
     }
 };

发表于 2015-08-10 00:02:54 回复(0)
首先,所求是最大子串,不是子序列,说明是连续的。
LS问题,用动态规划思想,把大问题分解成若干小问题,用矩阵记录状态结果
若s是两个字符串s1和s2敏感词有的字符,s1中s左侧的字符串为s1',s2中s左侧的字符串为s2',那么截止到s为止,LS(s1, s2) = LS(s1', s2')+1,用矩阵记录结果,例如babc 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)