19 lines
594 B
Python
19 lines
594 B
Python
def lcs(a, b):
|
|
# generate matrix of length of longest common subsequence for substrings of both words
|
|
lengths = [[0] * (len(b)+1) for _ in range(len(a)+1)]
|
|
for i, x in enumerate(a):
|
|
for j, y in enumerate(b):
|
|
if x == y:
|
|
lengths[i+1][j+1] = lengths[i][j] + 1
|
|
else:
|
|
lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])
|
|
|
|
# read a substring from the matrix
|
|
result = ''
|
|
j = len(b)
|
|
for i in range(1, len(a)+1):
|
|
if lengths[i][j] != lengths[i-1][j]:
|
|
result += a[i-1]
|
|
|
|
return result
|