首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串

热度指数：12532 时间限制：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)

Java

阿尼亚瓦库瓦库

import java.util.*;

public class LongestSubstring {
    // 动态规划解决最长公共子串问题：
    public int findLongest(String A, int n, String B, int m) {

        if (A.length() == 0 || n == 0 || B.length() == 0 || m == 0) {
            return 0;
        }

        int[][] dp = new int[A.length() + 1][B.length() + 1];

        int maxLength = 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] + 1; // 如果相同那就在上一个字母结果上加一
                    if (maxLength < dp[i + 1][j + 1]) {
                        maxLength = dp[i + 1][j + 1];
                    }
                }
            }
        }

        return maxLength;
    }
}

发表于 2021-05-07 17:00:32 回复(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)

Java

forcht

dp[i][j]表示以A[i],B[j]结尾的字符串，的是最大公共子串

public int findLongest(String A, int n, String B, int m) {
            int max=0;
            int[][] dp=new int[n][m];
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    if(A.charAt(i)==B.charAt(j)) {
                        dp[i][j]=(i>=1&&j>=1)?dp[i-1][j-1]+1:1;
                        if(max<dp[i][j])max=dp[i][j];
                    }else {
                        dp[i][j]=0;
                    }
                }
            }
            return max;
      }

发表于 2018-08-20 13:51:07 回复(0)

Java

天才小肥猫

import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        // write code here
        int maxLen = 0;
        int[] line = new int[m + 1];
//        int pos = 0;

        for (int i = 0; i < n; i++) {
            for (int j = m; j > 0; j--) {
                if (A.charAt(i) == B.charAt(j - 1)) {
                    line[j] = line[j - 1] + 1;
                    if (line[j] > maxLen) {
                        maxLen = line[j];
//                        pos = j - 1;
                    }
                } else {
                    line[j] = 0;
                }
            }
        }

//        System.out.println(B.substring(pos - maxLen + 1, pos + 1));
        return maxLen;
    }
}

和大家思路一样，矩阵斜对角线，只不过用一行去代表整个矩阵，这一点优化。

发表于 2018-04-04 14:33:20 回复(0)

Java

詆調壹點

import java.util.*;
public class LongestSubstring {
    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 = 0; 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;
					max = Math.max(dp[i][j], max);
				}
			}
		}
        return max;
    }
}

发表于 2016-09-10 12:16:02 回复(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)

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)