博客

求2个字符串的最大公共子序列（可不连续）

比如：a = ‘ABCBDAB’ ，b = ‘BDCABA’，公共子序列为‘BCBA’

这2篇文章写的很好：

原理讲解

python代码书写

def LCS_str(s1,s2):
    n = len(s1)
    m = len(s2)
    arr = [[0 for i in range(m+1)] for j in range(n+1)]
    flag = [[0 for i in range(m+1)] for j in range(n+1)]
    
    for i in range(n):
        for j in range(m):
            if s1[i] == s2[j]:      #如果2个字符相等，加1
                arr[i+1][j+1] = arr[i][j]+1
                flag[i+1][j+1] = 'ok'
            elif arr[i+1][j]>arr[i][j+1]:   
                arr[i+1][j+1] = arr[i+1][j]                
                flag[i+1][j+1] = 'left'
            else:
                arr[i+1][j+1] = arr[i][j+1]
                flag[i+1][j+1] = 'up'
    return arr,flag

#print(LCS_str(a,b))

def printLCS(flag,a,i,j):
    if i==0 or j==0:
        return
    if flag[i][j]=='ok':
        printLCS(flag,a,i-1,j-1)
        print(a[i-1],end='')
    elif flag[i][j]=='left':
        printLCS(flag,a,i,j-1)
    else:
        printLCS(flag,a,i-1,j)
        
#a = [1,3,4,5,6,7,7,8]
#b = [3,5,7,4,8,6,7,8,2] 
a = 'ABCBDAB'
b = 'BDCABA' 
c,flag = LCS_str(a,b)
printLCS(flag,a,len(a),len(b))

print('================')
for i in c:
    print(i)
print('---------------')
for i in flag:
    print(i)