Detailed example of Python using backtracking method subset tree template to obtain the longest common subsequence problem

This article mainly introduces the method of Python using the backtracking method subset tree template to obtain the longest common subsequence (LCS). It briefly describes the longest common subsequence problem and analyzes Python based on the backtracking method subset tree template in the form of examples. For the steps and related precautions for obtaining the longest common subsequence, friends in need can refer to the following

This article describes the method of using the backtracking subset tree template to obtain the longest common subsequence (LCS) in Python. Share it with everyone for your reference, the details are as follows:

Question

Enter

No. 1 Line: String A
Line 2: String B
(length of A,B

Output

Output the longest If there are multiple subsequences, output one at will.

Input example

belong
cnblogs

Output example

blog

Analysis

Since we plan to apply the backtracking method subset tree template, we must use the element-state space analysis method.

Use the characters in the string with a smaller length as elements and the characters in the string with a larger length as the state space. For each element, traverse its state space and leave other things to the shear. Branch function! ! !

Solution The length of x is not fixed, and xi represents the sequence number in string b.

When processing each element, if no state is selected (no character in cnblogs is selected), then the program cannot go to the next element.

This is indeed a big trouble! ! ! After thinking for a day, I finally figured out a way: expand the state space and add a state q! If the element selects state q, it is legal. However, state q is not added to solution x! ! !

Look at an intuitive picture:

At this point, enjoy it!

Code

'''最长公共子序列'''
# 作者：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，构造最长子序列lcs
def get_lcs(x):
  global b
  return &#39;&#39;.join([b[i] for i in x])
# 测试
LCS(0)
print(b)
print(best_x)
print(get_lcs(best_x))

Rendering

##

The above is the detailed content of Detailed example of Python using backtracking method subset tree template to obtain the longest common subsequence problem. For more information, please follow other related articles on the PHP Chinese website!