'''最長公共子序列'''
# 作者：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)cs
def 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))