Python實現最長公共子序列演算法

一、引言

最長公共子序列是字元串處理中的基本問題之一，可以用於計算兩個字元串之間的相似度或複製、粘貼代碼時檢測差異。而Python是一種廣泛使用的高級編程語言，擁有豐富的數據結構和庫函數支持。在本篇文章中，我們將展示如何使用Python實現最長公共子序列演算法。

二、什麼是最長公共子序列

在字元串處理中，最長公共子序列是指給定兩個字元串S1和S2，找到一個最長的子序列LCS（Longest Common Subsequence），滿足LCS同時是S1和S2的子序列。例如，S1=”ABCBDAB”和S2=”BDCABA”，它們的一個LCS是”BCBA”。

三、最長公共子序列演算法原理

最長公共子序列演算法可以使用動態規劃的思想來解決。假設S1的長度為m，S2的長度為n，且令C[i, j]表示S1[1, i]和S2[1, j]的最長公共子序列長度，其中1 ≤ i ≤ m，1 ≤ j ≤ n。那麼，可以使用以下遞推公式來求解C[i, j]：

if S1[i] == S2[j]:
    C[i][j] = C[i-1][j-1] + 1
else:
    C[i][j] = max(C[i][j-1], C[i-1][j])

其中，如果S1[i]等於S2[j]，那麼C[i][j]的值就等於C[i-1][j-1]加1；否則C[i][j]的值就等於C[i-1][j]和C[i][j-1]中的較大值。最終的最長公共子序列就可以通過反向求解的方式得到。

四、Python代碼實現

下面是Python實現最長公共子序列演算法的代碼：

def lcs(S1, S2):
    m = len(S1)
    n = len(S2)
    C = [[0] * (n + 1) for i in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if S1[i-1] == S2[j-1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j-1], C[i-1][j])
    result = ""
    i, j = m, n
    while i > 0 and j > 0:
        if S1[i-1] == S2[j-1]:
            result = S1[i-1] + result
            i -= 1
            j -= 1
        elif C[i-1][j] > C[i][j-1]:
            i -= 1
        else:
            j -= 1
    return result

S1 = "ABCBDAB"
S2 = "BDCABA"
print(lcs(S1, S2)) # 輸出 "BCBA"

五、總結

在本篇文章中，我們介紹了最長公共子序列的基本概念和演算法原理。通過Python實現，我們可以使用動態規劃的思想來求解最長公共子序列問題。希望這篇文章能夠幫助你更好地理解最長公共子序列演算法。