題目：

?

給定兩個(gè)序列X和Y,返回最長連續(xù)的公共子序列長度。如果沒有連續(xù)公共子序列，返回0.

X和Y的元素都是整數(shù)。

示例：

輸入：

1 5 7 3 4 5
7 3 4 4 5 7 -2

輸出：

3

?說明：

最長的連續(xù)公共子序列是[7,3,4] (X[2:4] 和Y[0:2])

這道題在【leetcode1143】的基礎(chǔ)上增加了公共子序列連續(xù)的限制。解法可以有以下幾種：

題解：

1. 動態(tài)規(guī)劃

創(chuàng)建m+1 行?n+1 列的二維數(shù)組dp，其中?dp[i][j] 表示 a和b分別以a[i-1],b[j-1]結(jié)尾的最長公共子序列的長度。

可以得到狀態(tài)轉(zhuǎn)移方程如下：

最終計(jì)算dp中的最大值即為最長公共連續(xù)子序列的長度。

def findLength(a,b):
    m,n=len(a),len(b)
    maxlength=0
    dp=[[0]*(n+1) for i in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if a[i-1]==b[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
                maxlength=max(maxlength,dp[i][j])
    return maxlength

時(shí)間復(fù)雜度：O(mn)

空間復(fù)雜度：O(mn),可以優(yōu)化至O(m)或O(n)(只存儲dp矩陣的兩列進(jìn)行計(jì)算）

2. 后綴數(shù)組

def longestCommonSubstring(A, B):
    if A == None or B == None:
        return
    C = [9999]
    s = A + C + B
    indexOfSharp = len(A)
    SA = suffixArray(s)
    maxLen, maxIndex = 0, 0
    hasCommon = False
    for i in range(len(s) - 1):
        # 判斷后綴數(shù)組中兩個(gè)相鄰元素對應(yīng)的后綴字符串是否位于“#”兩側(cè)，即是否屬于A和B兩個(gè)不同字符串
        diff = (SA[i] - indexOfSharp) * (SA[i + 1] - indexOfSharp)
        if diff < 0:
            tempLen = comlen(s, SA[i], SA[i + 1])
            if tempLen > maxLen:
                maxLen = tempLen
                maxIndex = SA[i]
                hasCommon = True
    return (maxLen, s[maxIndex:maxIndex + maxLen]) if hasCommon else False
# 得到一個(gè)字符串的后綴數(shù)組
def suffixArray(s):
    if s == None or len(s) == 0:
        return None
    allSuffix = []
    for i in range(len(s)):
        allSuffix.append([s[i:], i])
    sortedList = sorted(allSuffix)
    SA = [w[1] for w in sortedList]
    return SA
# 比較得到后綴數(shù)組中兩個(gè)相鄰的元素分別對應(yīng)的后綴字符串的最長前綴
def comlen(s, p, q):
    j = 0
    while j < len(s[p:]) and j < len(s[q:]) and s[p:p + j + 1] == s[q:q + j + 1]:
        j += 1
    return j

時(shí)間復(fù)雜度：O(nlgn)

空間復(fù)雜度：O(n^2)

3. 哈希表+二分查找

設(shè)最長公共子串的長度為x，那么x在0到min（len(X),len(Y))之間，并且滿足二分的性質(zhì)。因?yàn)槿绻嬖陂L度為m的公共子序列，那么必然存在長度小于m的公共子序列。先哈希一下這兩個(gè)序列，二分長度。每次check的時(shí)候，假設(shè)判斷是否存在長度為k的公共子串，那么看字符串1和字符串2長度為k的子串的哈希值有沒有相同的，如果有返回true，沒有返回false；然后使用二分查找最長公共子串長度x.

def findLen(X, Y):
    base, mod = 113, 10**9 + 9

    def checkHash(l):

        # Construct hash value set of X[0:l]
        hx = 0
        for i in range(l):
            hx = (hx * base + X[i]) % mod
        hvx = {hx}
        pow_base = pow(base, l - 1, mod)
        for i in range(l, len(X)):
            hx = ((hx - X[i - l] * pow_base) * base + X[i]) % mod
            hvx.add(hx)
        
        # Construct hash value set of Y[0:l] and check whether there is an hash value that matches 
        hy = 0
        for i in range(l):
            hy = (hy * base + Y[i]) % mod
        if hy in hvx:
            return True
        for i in range(l, len(Y)):
            hy = ((hy - Y[i - l] * pow_base) * base + Y[i]) % mod
            if hy in hvx:
                return True

        return False

    # Binary Search
    l, r = 0, min(len(X), len(Y))
    res = 0
    while l <= r:
        m = (l + r) // 2
        if checkHash(m):
            res = m
            l = m + 1
        else:
            r = m - 1
    return res

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(n)

4.雙指針文章來源地址http://www.zghlxwxcb.cn/news/detail-690525.html

def findLength(a, b):
    aa = ''.join(a)
    l, s = 1, 0
    l1, l2 = len(a), len(b)
    rtn = 0
    while l <= l1 and l+s <= l2:
        e = s + l
        temp = ''.join(b[s:e])
        if temp in aa:
            rtn = max(rtn, l)
            l += 1
        else:
           if str(b[e-1]) not in aa:
                s = e
           else:
                s += 1
                
           if s + rtn >= l2:
                return rtn
    return rtn

到了這里，關(guān)于【python】求最長連續(xù)公共子序列長度的幾種解法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！