INT102-Longes-Common-Subsequences Dynamic Programming

 1 import numpy as np
 2 
 3 
 4 def LCS(X: str, Y: str) -> tuple:
 5     n, m = len(X), len(Y)
 6     dp = [[0 for col in range(m + 1)] for row in range(n + 1)]
 7     flag = [[" " for col in range(m + 1)] for row in range(n + 1)]
 8     for i in range(n):
 9         for j in range(m):
10             if X[i] == Y[j]:
11                 dp[i + 1][j + 1] = dp[i][j] + 1
12                 flag[i + 1][j + 1] = '↖'
13             elif dp[i + 1][j] > dp[i][j + 1]:
14                 dp[i + 1][j + 1] = dp[i + 1][j]
15                 flag[i + 1][j + 1] = '←'
16             else:
17                 dp[i + 1][j + 1] = dp[i][j + 1]
18                 flag[i + 1][j + 1] = '↑'
19     return dp, flag
20 
21 
22 if __name__ == '__main__':
23     X = "GAGT"
24     Y = "AGCCCT"
25     dp, flag = LCS(X, Y)
26     print(np.array(dp))
27     print(np.array(flag))