最长公共子序列问题python,伪代码和代码
时间: 2023-07-10 07:26:31 浏览: 42
伪代码:
```
function LCS(X[1..m], Y[1..n])
C = array(0, [0..m, 0..n])
for i := 1..m
for j := 1..n
if X[i] == Y[j]
C[i,j] := C[i-1,j-1] + 1
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
```
Python代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
C = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
C[i][j] = C[i-1][j-1] + 1
else:
C[i][j] = max(C[i][j-1], C[i-1][j])
return C[m][n]
```
其中,`X`和`Y`是需要比较的两个字符串,函数返回它们的最长公共子序列的长度。
相关问题
最长公共子序列问题python源代码
def lcs(x, y):
m = len(x)
n = len(y)
c = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i][j - 1], c[i - 1][j])
return c[m][n]
动态规划算法求最长公共子序列问题python完整代码
下面是Python的完整代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j] , L[i][j-1])
index = L[m][n]
lcs = [""] * (index+1)
lcs[index] = ""
i = m
j = n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i-=1
j-=1
index-=1
elif L[i-1][j] > L[i][j-1]:
i-=1
else:
j-=1
return "".join(lcs)
X = "AGGTAB"
Y = "GXTXAYB"
print("LCS of", X, "and", Y, "is", lcs(X, Y))
```
其中,X和Y分别为两个字符串,lcs函数返回它们的最长公共子序列。该算法的时间复杂度为O(mn),其中m和n分别为X和Y的长度。