Python如何求解最长公共子序列

Python-求解两个字符串的最长公共子序列

一、问题描述

给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA。

二、算法求解

这是一个动态规划的题目。对于可用动态规划求解的问题,一般有两个特征:①最优子结构;②重叠子问题

①最优子结构

设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y)

找出LCS(X,Y)就是一个最优化问题。因为,我们需要找到X和Y中最长的那个公共子序列。而要找X和Y的LCS,首先考虑X的最后一个元素和Y的最后一个元素。

(1)如果xn=ym,即X的最后一个元素与Y的最后一个元素相同,这说明该元素一定位于公共子序列中。因此,现在只需要找:LCS(Xn-1,Ym-1)

LCS(Xn-1,Ym-1)就是原问题的一个子问题。为什么叫子问题?因为它的规模比原问题小。

为什么是最优的子问题?因为我们要找的是Xn-1和Ym-1的最长公共子序列啊。最长的!换句话说就是最优的那个。

(2)如果xn!=ym,这下要麻烦一点,因为它产生了两个子问题:LCS(Xn-1,Ym)和LCS(Xn,Ym-1)

因为序列X和序列Y的最后一个元素不相等,那说明最后一个元素不可能是最长公共子序列中的元素。

LCS(Xn-1,Ym)表示:最长公共序列可以在(x1,x2,...xn-1)和(y1,y2,...,ym)中找。

LCS(Xn,Ym-1)表示:最长公共序列可以在(x1,x2,...xn)和(y1,y2,...,ym-1)中找。

求解上面两个子问题,得到的公共子序列谁最长,那谁就是LCS(X,Y)。用数学表示就是:

LCS=max{LCS(Xn-1,Ym),LCS(Xn,Ym-1)}

由于条件⑴和⑵考虑到了所有可能的情况。因此,我们成功的把原问题转化成了三个规模更小的问题。

②重叠子问题

重叠子问题是什么?就是说原问题转化成子问题后,子问题中有相同的问题。

原问题是:LCS(X,Y)。子问题有❶LCS(Xn-1,Ym-1)❷ LCS(Xn-1,Ym)❸ LCS(Xn,Ym-1)

乍一看,这三个问题是不重叠的。可本质上它们是重叠的,因为它们只重叠了一大部分。举例:

第二个子问题:LCS(Xn-1,Ym)就包含了问题❶LCS(Xn-1,Ym-1),为什么?

因为,当Xn-1和Ym的最后一个元素不相同时,我们又需要将LCS(Xn-1,Ym-1)进行分解:分解成:LCS(Xn-1,Ym-1)和LCS(Xn-2,Ym)

也就是说:在子问题的继续分解中,有些问题是重叠的。

由于像LCS这样的问题,它具有重叠子问题的性质,因此:用递归来求解就太不划算了。国为采用递归,它重复地求解了子问题,而且需要注意的是,所有子问题加起来的个数是指数级的。

那么问题来了,如果用递归求解,有指数级个子问题,故时间复杂度是指数级的。这指数级个子问题,难道用了动态规划,就变成多项式时间了??

关键是采用动态规划时,并不需要去一一计算那些重叠了的子问题。或者说:用了动态规划之后,有些子问题是通过“查表”直接得到的,而不是重新又计算一遍得到的。举个例子:比如求Fib数列。

zz.png

求fib(5),分解成了两个子问题:fib(4)和fib(3),求解fib(4)和fib(3)时,又分解了一系列的小问题...

从图中可以看出:根的左右子树:fib(4)和fib(3)下,是有很多重叠的!比如,对于fib(2),它就一共出现了三次。如果用递归来求解,fib(2)就会被计算三次,而用DP(Dynamic Programming)动态规划,则fib(2)只会计算一次,其他两次则是通过“查表”直接求得。而且,更关键的是:查找求得该问题的解之后,就不需要再继续去分解该问题了。而对于递归,是不断地将问题解,直到分解为基准问题(fib(0)或者fib(1))

说了这么多,还是写下最长公共子序列的递归式才完整。

xx.png

C[i,j]表示:(x1,x2,...,xi)和(y1,y2,...,yj)的最长公共子序列的长度。公式的具体解释可参考《算法导论》动态规划章节

三、LCS Python代码实现

#! /usr/bin/env python3
# -*- coding:utf-8 -*-
# Note     : 用于实现求解两个字符串的最长公共子序列
def longestCommonSequence(str_one, str_two, case_sensitive=True):
    """
    str_one 和 str_two 的最长公共子序列
    :param str_one: 字符串1
    :param str_two: 字符串2(正确结果)
    :param case_sensitive: 比较时是否区分大小写,默认区分大小写
    :return: 最长公共子序列的长度
    """
    len_str1 = len(str_one)
    len_str2 = len(str_two)
    # 定义一个列表来保存最长公共子序列的长度,并初始化
    record = [[0 for i in range(len_str2 + 1)] for j in range(len_str1 + 1)]
    for i in range(len_str1):
        for j in range(len_str2):
            if str_one[i] == str_two[j]:
                record[i + 1][j + 1] = record[i][j] + 1
            elif record[i + 1][j] > record[i][j + 1]:
                record[i + 1][j + 1] = record[i + 1][j]
            else:
                record[i + 1][j + 1] = record[i][j + 1]
    return record[-1][-1]
if __name__ == '__main__':
    # 字符串1
    s1 = "BDCABA"
    # 字符串2
    s2 = "ABCBDAB"
    # 计算最长公共子序列的长度
    res = longestCommonSequence(s1, s2)
    # 打印结果
    print(res) # 4

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/298229.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

GPT实战系列-大模型为我所用之借用ChatGLM3构建查询助手

GPT实战系列-https://blog.csdn.net/alex_starsky/category_12467518.html 如何使用大模型查询助手功能?例如调用工具实现网络查询助手功能。目前只有 ChatGLM3-6B 模型支持工具调用,而 ChatGLM3-6B-Base 和 ChatGLM3-6B-32K 模型不支持。 定义好工具的…

【Android取证篇】小米手机OTG取证知识

【Android取证篇】小米手机OTG取证知识 小米手机OTG使用方法—【蘇小沐】 目录 1、OTG用途 2、手机连不上U盘 3、小米手机有没有OTG 4、手机usb调试找不到 5、MHL能否在HDMI输出视频的同时进行USB传输 1、OTG用途 使用OTG外接设备,需要使用和手机接口对应匹配的…

一起学docker(六)| docker网络

Docker网络 不启动docker,网络情况: 启动docker,网络情况: 作用 容器间的互联和通信以及端口映射容器IP变动时候可以通过服务名直接网络通信而不受影响 常用命令 docker network --help 查看docker网络相关命令docker network…

C++——STL标准模板库——容器详解——stack+queue

一、基本概念 (一)stack(栈或堆栈) 一种只允许同一端进出的线性数据结构,数据先进后出。基本模型类似于瓶子。 (二)queue(队列) 一种只允许一端进、另一端出的线性数…

Tomcat服务为什么起不来?

转载说明:如果您喜欢这篇文章并打算转载它,请私信作者取得授权。感谢您喜爱本文,请文明转载,谢谢。 服务跑在Tomcat下面,有时候会遇到Tomcat起不来的情况。目前为止常遇到的情况有如下几种: 1. Tomcat服务…

Linux第11步_解决“挂载后的U盘出现中文乱码”

学习完“通过终端挂载和卸载U盘”,我们发现U盘下的中文文件名会出现乱码,现在讲解怎么解决这个问题。其实就是复习一下“通过终端挂载和卸载U盘”,单独讲解,是为了解决问题,一次性搞好,我们会不长记性。 在…

无心剑七绝《高斯黎曼》

七绝高斯黎曼 高耸云端四海惊 斯人伟绩震豪英 黎霞璀璨通灵处 曼妙方程万世名 2024年1月6日 平水韵八庚平韵 《七绝高斯黎曼》是无心剑所作的一首以数学家为主题的七言绝句。全诗巧妙地将两位杰出的数学家——高斯(Carl Friedrich Gauss)与黎曼&#…

性能优化-OpenMP基础教程(三)

本文主要介绍OpenMP并行编程的环境变量和实战、主要对比理解嵌套并行的效果。 🎬个人简介:一个全栈工程师的升级之路! 📋个人专栏:高性能(HPC)开发基础教程 🎀CSDN主页 发狂的小花 &…

HarmonyOS 应用开发学习笔记 stateStyles:多态样式

1、 HarmoryOS Ability页面的生命周期 2、 Component自定义组件 3、HarmonyOS 应用开发学习笔记 ets组件生命周期 4、HarmonyOS 应用开发学习笔记 ets组件样式定义 Styles装饰器:定义组件重用样式 Extend装饰器:定义扩展组件样式 前面记录了ets组件样式…

基于粒子群算法的曲面路径优化

目录 摘要 测试函数shubert 粒子群算法的原理 粒子群算法的主要参数 粒子群算法原理 粒子群算法参数拟合 代码 结果分析 展望 基于粒子群算法的曲面路径优化(代码完整,数据齐全)资源-CSDN文库 https://download.csdn.net/download/abc991835105/88698419 摘要 寻优算法,…

Guarded Suspension模式--适合等待事件处理

Guarded是被守护、被保卫、被保护的意思, Suspension则是暂停的意思。 如果执行现在的处理会造成问题, 就让执行处理的线程进行等待--- 这就是Guarded Suspension模式。 模式通过让线程等待来保证实例的安全性。 一个线程ClientThread会将请求 Request的…

Linux第16步_安装NFS服务

NFS(Network File System)是一种在网络上实现的分布式文件系统,它允许不同的操作系统和设备之间共享文件和资源。 在创建的linux目录下,再创建一个“nfs“文件夹,用来供nfs服务器使用,便于”我们的开发板“…

C语言注意点(2)

1.使用pow函数的相关问题 局部变量n0 while(num/pow(10,n)) n; 为什么不可行 printf("%d",num/pow(10,4)%10) 为什么要提前用temp先引出来 答:pow函数的返回值为double类型,1.终止条件不会满足 2.num/pow(10,4)结果为浮点型,浮…

Nginx 常用变量 与 防盗链

目录 1.常用变量 2. $http_referer 配置防盗链 2.1 referer 2.2 配置防盗链 1.常用变量 变量说明 $args 请求中的参数,也叫查询参数 $content_length HTTP响应信息里的"Content-Length" $document_root nginx虚拟主机配置文件中的root站点根目录…

STM32的在线升级(IAP)实现方法:BOOT+APP原理详解

0 工具准备 Keil uVision5 Cortex M3权威指南(中文) STM32参考手册 1 在线升级(IAP)设计思路 为了实现STM32的在线升级(IAP)功能,通常会将STM32的FLASH划分为BOOT和APP两个部分,BOO…

JavaScript:关系数组、对象的复制

关系数组(关联数组)解字符串出现的次数: var str aaccddvvasdadqwd;// 统计每个字母出现的次数// 关系数组(关联数组) 长度永远为0// 使用字符串当做索引var arr [];arr[0] 20;// arr[a] 1;// arr[b] 3;// arr[c] 4;// console.log(arr)for (var i 0; i < str.lengt…

美经济学家预测,明年美股或将大跌86%,你怎么看?

年初至今&#xff0c;标准普尔500指数上涨25%&#xff0c;道琼斯指数上涨13%&#xff0c;以科技股为主的纳斯达克指数大涨了44%。 美国经济学家哈里斯登特近日预测&#xff0c;这种牛市是“100%人为印钞的结果”&#xff0c;而这一巨大的泡沫将在2024年破灭&#xff0c;届时美…

“智慧”千里眼助力水泵站

泵站是为水提供势能和压能&#xff0c;解决无自流条件下的排灌、供水和水资源调配问题的唯一动力来源&#xff0c;在工农业用水、防洪、排涝和抗旱减灾等方面发挥着重要作用。一旦出现异常&#xff0c;对经济生产将造成难以估量的损失&#xff0c;给水利安全管理造成负担。因此…

反射UnityEditor.GameView设置GamePlayMode分辨率

现在很有游戏考虑横屏适配、竖屏适配、阿拉伯语适配&#xff08;横竖屏&#xff09;导致拼界面变得越来越繁琐。 有很多时候需要记录各个控件的状态。 为了减少操作&#xff0c;特意制作了这个工具&#xff0c;点击用x配置可以自动切换到 宽高分辨率&#xff0c;如果当前没有则…

简易视频播放器(案例)

介绍 本篇Codelab使用ArkTS语言实现视频播放器&#xff0c;主要包括主界面和视频播放界面&#xff0c;我们将一起完成以下功能&#xff1a; 主界面顶部使用Swiper组件实现视频海报轮播。主界面下方使用List组件实现视频列表。播放界面使用Video组件实现视频播放。在不使用视频组…