首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串

热度指数：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)

Python

sk_1kgn

class LongestSubstring:
def findLongest(self, A, n, B, m):
# write code here
# 以短试长
if n > m:
A, B, n, m = B, A, m, n
count = 0
# 左右逐次切片缩短
for i in range(n):
for j in range(n-i):
if A[i:][:n-i-j] in B:
count = max(count, len(A[i:][:n-i-j]))
#break

return count

不太懂时间复杂度的算法，请问以上实现的复杂度是多少？是m*n吗？来个好心的有缘人告诉我一下呗

发表于 2020-02-19 15:58:18 回复(0)

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)

Python

离疏

# -*- coding:utf-8 -*-
class LongestSubstring:
    def findLongest(self, A, n, B, m):
        dp=[[0 for i in range(n)]for j in range(m)]#用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况
        l=0
        for i in range(m):
            for j in range(n):
                if B[i]==A[j]:#当字符匹配的时候，赋上其左上角元素的值加一
                    if j==0 or i==0:
                        dp[i][j]=1
                    else:
                        dp[i][j]=dp[i-1][j-1]+1
                    if dp[i][j]>l:#判断当前生成的元素的值是不是最大的
                        l=dp[i][j]
        return l

发表于 2018-08-16 18:16:58 回复(0)

Python

Py_璐爷

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        # write code here
        mat = [[0 for i in range(m+1)] for j in range(n+1)]
        max_val = 0
        for i in range(1, n+1):
            for j in range(1, m+1):
                if A[i-1] == B[j-1]:
                    mat[i][j] = mat[i-1][j-1] + 1
                    if mat[i][j] > max_val:
                        max_val = mat[i][j]
        return max_val

发表于 2018-03-11 17:19:24 回复(0)

Python

offer到碗里

# -*- coding:utf-8 -*-

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        # write code here
        #新建一个m行n列的矩阵
        matrix = [0] * m * n
        #1、矩阵的第一行，即matrix[0][i]，代表str1[0]与str2[0...n]的最长公共子串.
        # str2[0]只有一个字符，所以matrix[i][0]最大为1
        for i in range(n):
            if A[i] == B[0]:
                matrix[i] = 1
        #2、矩阵的第一列，matrix[i][0]最大为1
        for i in range(m):
            if B[i] == A[0]:
                matrix[i*n] = 1
        #3、其他位置
        max = 0
        for i in range(1,m):
            for j in range(1,n):
                if B[i] == A[j]:
                    matrix[i*n+j] = matrix[(i-1)*n+j-1]+1
                    if max<matrix[i*n+j]:
                        max = matrix[i*n+j]
        print matrix
        return max

发表于 2018-01-24 09:04:18 回复(0)

Python

izayacode

l(i,j)是以A[i]和B[j]开头的最长公共串的长度， longest = max l(i,j)，虚拟边界：i=n or j = m，l(n,)=l(,m)=0

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        l = [[0 for j in range(m+1)] for i in range(n+1)]
        #注意：虚拟边界：i=n or j = m，l(n,)=l(,m)=0
        longest = 0
        for i in range(n-1,-1,-1):   #n-1,...,1,0
            for j in range(m-1,-1,-1):   #m-1,...,1,0
                if A[i]==B[j]:
                    l[i][j] = 1+l[i+1][j+1]
                    #find max l(i,j)
                    if l[i][j]>longest:
                        longest = l[i][j]
                else:
                    l[i][j] = 0
        return longest

发表于 2016-08-10 15:18:09 回复(0)