本文实例讲述了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，构造最长子序列lcs
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))

效果图

更多关于Python相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

# Python  # 回溯法  # 子集树模板  # 最长公共子序列  # LCS  # Python求两个字符串最长公共子序列代码实例  # 详解Python最长公共子串和最长公共子序列的实现  # python实现最长公共子序列  # Python 中最长公共子序列的长度  # 遍历  # 递归  # 进阶  # 操作技巧  # 是个  # 相关内容  # 多个  # 它是  # 数据结构  # 给大家  # 如果没有  # 较小  # 想出  # 相对于  # 更多关于  # 所述  # 程序设计  # 使用技巧  # 靠前  # 没一个 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何快速搭建二级域名独立网站？  如何登录建站主机？访问步骤全解析  利用python获取某年中每个月的第一天和最后一天  如何在腾讯云免费申请建站？  LinuxShell函数封装方法_脚本复用设计思路【教程】  网站图片在线制作软件,怎么在图片上做链接？  Laravel如何实现API资源集合？（Resource Collection教程）  Laravel中的withCount方法怎么高效统计关联模型数量  5种Android数据存储方式汇总  大同网页,大同瑞慈医院官网？  Win11怎么关闭资讯和兴趣_Windows11任务栏设置隐藏小组件  Laravel Sail是什么_基于Docker的Laravel本地开发环境Sail入门  奇安信“盘古石”团队突破 iOS 26.1 提权  如何快速生成可下载的建站源码工具？  Laravel模型关联查询教程_Laravel Eloquent一对多关联写法  深圳网站制作平台,深圳市做网站好的公司有哪些？  阿里云高弹*务器配置方案｜支持分布式架构与多节点部署  Laravel怎么实现前端Toast弹窗提示_Laravel Session闪存数据Flash传递给前端【方法】  如何快速辨别茅台真假？关键步骤解析  如何快速上传建站程序避免常见错误？  网站制作公司哪里好做,成都网站制作公司哪家做得比较好，更正规？  html5如何实现懒加载图片_ intersectionobserver api用法【教程】  Internet Explorer官网直接进入 IE浏览器在线体验版网址  如何在景安云服务器上绑定域名并配置虚拟主机？  Laravel怎么配置.env环境变量_Laravel生产环境敏感数据保护与读取【方法】  如何打造高效商业网站？建站目的决定转化率  php 三元运算符实例详细介绍  Windows驱动无法加载错误解决方法_驱动签名验证失败处理步骤  Laravel Eloquent性能优化技巧_Laravel N+1查询问题解决  HTML5建模怎么导出为FBX格式_FBX格式兼容性及导出步骤【指南】  Laravel如何处理JSON字段_Eloquent原生JSON字段类型操作教程  Laravel怎么导出Excel文件_Laravel Excel插件使用教程  香港服务器选型指南：免备案配置与高效建站方案解析  Laravel如何使用Spatie Media Library_Laravel图片上传管理与缩略图生成【步骤】  香港服务器网站推广：SEO优化与外贸独立站搭建策略  Windows10怎样连接蓝牙设备_Windows10蓝牙连接步骤【教程】  如何制作公司的网站链接,公司想做一个网站，一般需要花多少钱？  WordPress 子目录安装中正确处理脚本路径的完整指南  如何做网站制作流程,*游戏网站怎么搭建？  使用spring连接及操作mongodb3.0实例  Zeus浏览器网页版官网入口 宙斯浏览器官网在线通道  Android自定义控件实现温度旋转按钮效果  jimdo怎样用html5做选项卡_jimdo选项卡html5实现与切换效果【指南】  高防服务器租用指南：配置选择与快速部署攻略  作用域操作符会触发自动加载吗_php类自动加载机制与::调用【教程】  Win10如何卸载预装Edge扩展_Win10卸载Edge扩展教程【方法】  Laravel队列由Redis驱动怎么配置_Laravel Redis队列使用教程  动图在线制作网站有哪些,滑动动图图集怎么做？  浅析上传头像示例及其注意事项  Laravel如何实现API速率限制？（Rate Limiting教程）