实例详解Python使用回溯法子集树模板获取最长公共子序列问题

'''最长公共子序列'''# 作者：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] = 2 and x[-1]  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))