-
Notifications
You must be signed in to change notification settings - Fork 119
/
lcs_length.py
37 lines (35 loc) · 1.01 KB
/
lcs_length.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def lcs_length(X, Y):
m = len(X)
n = len(Y)
b = [[0 for x in xrange(n)] for y in xrange(m)]
c = [[0 for x in xrange(n+1)] for y in xrange(m+1)]
# for i in xrange(m+1):
# c[i][0] = 0
# for j in xrange(n+1):
# c[0][j] = 0
for i in xrange(1, m+1):
for j in xrange(1, n+1):
if X[i-1] == Y[j-1]:
c[i][j] = c[i-1][j-1] + 1
b[i-1][j-1] = "lu"
elif c[i-1][j] >= c[i][j-1]:
c[i][j] = c[i-1][j]
b[i-1][j-1] = "u"
else:
c[i][j] = c[i][j-1]
b[i-1][j-1] = "l"
return c, b
def print_lcs(b, X, i, j):
if i == 0 or j == 0:
return
if b[i-1][j-1] == "lu":
print_lcs(b, X, i-1, j-1)
print X[i-1]
elif b[i-1][j-1] == "u":
print_lcs(b, X, i-1, j)
else:
print_lcs(b, X, i, j-1)
X = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
Y = ['B', 'D', 'C', 'A', 'B', 'A']
(c, b) = lcs_length(X, Y)
print_lcs(b, X, len(X), len(Y))