def init(arr, n, m):
for i in range(n):
temp = [0] * m
arr.append(temp)
def LCS(a, b, n, m):
dp = []
h = []
init(dp, n, m)
init(h, n, m)
for i in range(1, n):
for j in range(1, m):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
h[i][j] = 0
else:
if dp[i][j - 1] >= dp[i - 1][j]:
dp[i][j] = dp[i][j - 1]
h[i][j] = 1
else:
dp[i][j] = dp[i - 1][j]
h[i][j] = 2
return dp, h
def LCSS(h, a, n, m):
i = n - 1
j = m - 1
res = ""
while i > 0 and j > 0:
if h[i][j] == 0:
res = a[i - 1] + res
i -= 1
j -= 1
elif h[i][j] == 1:
j -= 1
elif h[i][j] == 2:
i -= 1
return res
a = "abcbdacb"
b = "bdcab"
n = len(a) + 1
m = len(b) + 1
dp, h = LCS(a, b, n, m)
res = LCSS(h, a, n, m)
print(res)
