本文實例講述了Python使用回溯法子集樹模板獲取最長公共子序列（LCS）的方法。分享給大家供大家參考，具體如下：

問題

輸入

第1行：字符串A
第2行：字符串B
(A,B的長度 <= 1000)

輸出

輸出最長的子序列，如果有多個，隨意輸出1個。

輸入示例

belong
cnblogs

輸出示例

blog

分析

既然打算套用回溯法子集樹模板，那就要祭出元素-狀態空間分析大法。

以長度較小的字符串中的字符作為元素，以長度較大的字符串中的字符作為狀態空間，對每一個元素，遍歷它的狀態空間，其它的事情交給剪枝函數！！！

解x的長度不固定，xi表示字符串b中的序號。

在處理每一個元素時，如果沒有一個狀態被選擇（cnblogs中沒一個字符被選取），那么程序無法去往下一個元素。

這確實是個不小的麻煩！！！思考了一天，終于想出辦法了：擴充狀態空間，增加一個狀態q！如果元素選取了狀態q，它是合法的。但是，狀態q不加入解x內！！！

看一個直觀的圖：

至此，enjoy it!

代碼

'''最長公共子序列'''# 作者：hhh5460# 時間：2017年6月3日a = 'belong'b = 'cnblogs'x = []  # 一個解（長度不固定）xi是b中字符的序號X = []  # 一組解best_x = [] # 最佳解best_len = 0 # 最大子序列長度# 沖突檢測def conflict(k):  global n, x, X, a,b,best_len  # 如果兩個字符不相等  if x[-1] < len(b) and a[k] != b[x[-1]]:    return True  # 如果兩個字符相等，但是相對于前一個在b中的位置靠前  if a[k] == b[x[-1]] and (len(x) >= 2 and x[-1] <= x[-2]):    return True  # 如果部分解的長度加上后面a剩下的長度，小于等于best_len  if len(x) + (len(a)-k) < best_len:    return True  return False # 無沖突# 回溯法（遞歸版本）def LCS(k): # 到達a中的第k個元素  global x, X,a,b,best_len,best_x  #print(k, x)  if k == len(a): # 超出最尾的元素    if len(x) > best_len:      best_len = len(x)      best_x = x[:]  else:    for i in range(len(b)+1): # 遍歷 狀態空間：0~len(b)-1，技巧：人為增加一種狀態len(b)，表示改行沒有元素選取      if i==len(b): # 此狀態不放入解x內        LCS(k+1)      else:        x.append(i)        if not conflict(k): # 剪枝          LCS(k+1)        x.pop()       # 回溯# 根據一個解x，構造最長子序列lcsdef get_lcs(x):  global b  return ''.join([b[i] for i in x])# 測試LCS(0)print(b)print(best_x)print(get_lcs(best_x))

效果圖

更多關于Python相關內容可查看本站專題：《Python數據結構與算法教程》、《Python Socket編程技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》