题目：
给定两个序列X和Y,返回最长连续的公共子序列长度。如果没有连续公共子序列，返回0.
X和Y的元素都是整数。
示例：
输入：
1 5 7 3 4 5
7 3 4 4 5 7 -2
输出：
3
说明：
最长的连续公共子序列是[7,3,4] (X[2:4] 和Y[0:2])
这道题在【leetcode1143】的基础上增加了公共子序列连续的限制。解法可以有以下几种：
题解：
1. 动态规划
创建m+1 行 n+1 列的二维数组dp，其中 dp[i][j] 表示 a和b分别以a[i-1],b[j-1]结尾的最长公共子序列的长度。
可以得到状态转移方程如下：
最终计算dp中的最大值即为最长公共连续子序列的长度。
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时间复杂度：O(mn)
空间复杂度：O(mn),可以优化至O(m)或O(n)(只存储dp矩阵的两列进行计算）
2. 后缀数组
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):
# 判断后缀数组中两个相邻元素对应的后缀字符串是否位于“#”两侧，即是否属于A和B两个不同字符串
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
# 得到一个字符串的后缀数组
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
# 比较得到后缀数组中两个相邻的元素分别对应的后缀字符串的最长前缀
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时间复杂度：O(nlgn)
空间复杂度：O(n^2)
3. 哈希表+二分查找
设最长公共子串的长度为x，那么x在0到min（len(X),len(Y))之间，并且满足二分的性质。因为如果存在长度为m的公共子序列，那么必然存在长度小于m的公共子序列。先哈希一下这两个序列，二分长度。每次check的时候，假设判断是否存在长度为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时间复杂度：O(nlogn)
空间复杂度：O(n)文章来源：https://www.toymoban.com/news/detail-690525.html
4.双指针文章来源地址https://www.toymoban.com/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
到了这里，关于【python】求最长连续公共子序列长度的几种解法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
