本文实例讲述了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程序设计有所帮助。
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 孙悦.1996-伙伴【正大国际】【WAV+CUE】
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】