[ROSALIND] Longest Common Subsequence

原本 CLR 的 Print-LCS(b, X, i, j) 用 recursive function 寫的，有點蠢。

改用 stack 的概念重寫。

def longest_common_subsequence(s, t):
    c, b = longest_common_subsequence_table(s, t)
    return longest_common_subsequence_printable(b, s, len(s), len(t))

def longest_common_subsequence_table(s, t):
    m, n = len(s), len(t)
    b = [[0 for _ in range(n)] for _ in range(m)] 
    c = [[0 for _ in range(n+1)] for _ in range(m+1)] 
    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                c[i+1][j+1] = c[i][j] + 1
                b[i][j] = 'Diagonal'
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
                b[i][j] = 'Up'
            else:
                c[i+1][j+1] = c[i+1][j]
                b[i][j] = 'Left'
    return c, b

def longest_common_subsequence_printable(b, s, i, j):
    reversed_lcs = ''
    while True:
        if i == 0 or j == 0:
            break
        direction = b[i-1][j-1]
        if direction == 'Diagonal':
            lcs += s[i-1]
            i, j = i-1, j-1
        elif direction == 'Up':
            i, j = i-1, j
        else:
            i, j = i, j-1
    return reversed_lcs[::-1]