LCSの関数

関数の中身の解説は割愛しますが、s1 と s2 の文字列を指定すれば一発で問題解決します。

LCS(Longest-common subsequence problem)
最長部分列問題

文字列 S と T の共通部分列（S の部分列かつ T の部分列）のうち、
最長のものは何文字かとその文字列を出力する関数

def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    # memorization of m[l1][l2]
    m = []
    for x in range(l1+1):
        m.append([0]*(l2+1))

    # Fill 0th row
    isSameFound = False
    for i in range(l1):
        if isSameFound or s1[i] == s2[0]:
            m[i][0] = 1
            isSameFound = True
 
     # Fill 0th colum
    isSameFound = False
    for j in range(l2):
        if isSameFound or s2[j] == s1[0]:
            m[0][j] = 1
            isSameFound = True
    
    max_len = 0
    # m[i][j] stores(蓄える) the maximum length of subsequence(後続) of s1[:i+1], s2[:j+1]
    for i in range(0, l1-1):
        for j in range(0, l2-1):
            if s1[i+1] == s2[j+1]:
                m[i+1][j+1] = m[i][j] + 1
                max_len = max(m[i+1][j+1], max_len)
            else:
                m[i+1][j+1] = max(m[i][j+1], m[i+1][j])

#    for i in range(l1):
#        for j in range(l2):
#            print("{:3}".format(m[i][j]), end='  ')
#        print('')
    
    print(max_len)

    #If you want to know just the length of the lcs, return maxLen.
    #Here we'll try to print the lcs.
    lcs_str = ''
    i, j = l1-1, l2-1
    while i >= 0 and j >= 0:
        if s1[i] == s2[j]:
            lcs_str += s1[i] #or s2[j-1]
            i -= 1
            j -= 1
        else:
            if m[i-1][j] > m[i][j-1]:
                i -= 1
            else:
                j -= 1

    print(lcs_str[::-1])