'''最長公共子序列'''# 作者：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): # 遍歷 狀態(tài)空間：0~len(b)-1，技巧：人為增加一種狀態(tài)len(b)，表示改行沒有元素選取      if i==len(b): # 此狀態(tài)不放入解x內(nèi)        LCS(k+1)      else:        x.append(i)        if not conflict(k): # 剪枝          LCS(k+1)        x.pop()       # 回溯# 根據(jù)一個解x，構(gòu)造最長子序列l(wèi)csdef 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))