位置: 编程技术 - 正文

KMP算法精解及其Python版的代码示例(kmp算法理解)

编辑:rootadmin

推荐整理分享KMP算法精解及其Python版的代码示例(kmp算法理解),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:kmp算法理解,kmp算法 partial match table,kmp算法的概念,kmp算法 csdn,kmp算法简单例题,kmp算法 partial match table,kmp算法的概念,kmp算法 csdn,内容如对您有帮助,希望把文章链接给更多的朋友!

KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题。算法名称来源于发明者Knuth,Morris,Pratt。假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm)。

朴素的字符串查找方法从字符串S的第一个字符开始与M进行比较,如果匹配失败。从下一字符开始,重新比较。指导第 (ls - lm) 个字符。这种方法容易想到并且容易理解,效率不高。问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些。

KMP算法精解及其Python版的代码示例(kmp算法理解)

KMP的字符串查找方法假定在模式串的连续字串M[0, i] 且 i < lm,已经成功匹配字符串S。但是不巧第 i+1 个字符失败了,怎么办?移动一个字符,重头再来?当然不好,那就是朴素路线了。我们能否从跌倒的地方继续走呢?既然字串M[0 - i]已经匹配成功,那就从这个子串上做文章。举个栗子 S序号 j j + 1 j + 2 j + 3 j + 4 j + 5 j+6 j + 7 。。。 S串 a b c a b c d e 。。。 M串 a b c a b d

M序号

0 1 2 3 4 5 此时匹配失败在M串的第5个字符,前4个字符已经匹配成功。如果从跌倒的地方出发,则需要存在M[0, 4]的子串M[0, k] == S[j+4-k , j+4]。由于M[0, 4] == S[j , j+4] 则有 字串S[j+4-k, j+4] == M[4-k, 4]。综上有M[0, k] == M[4-k, 4]如果这样的k不存在,那就老老实实的朴素了。从上面的表格可以直观的看出,下一次匹配只要把M串移动到 j + 3 位置,从 j+5 开始匹配就可以。很容易看出来 在已经匹配成功的字串M[0 , 4]中有最长的子串 (M[0 , 1] == M[3 , 4]),这个就是问题的关键。因此KMP的核心部分就是计算模式串的各个子串的 k。

实例首先我们来看一下字符串的朴素匹配.可以想象成把文本串s固定住,模式串p从s最左边开始对齐,如果对齐的部分完全一样,则匹配成功,失败则将模式串p整体往右移1位,继续检查对齐部分,如此反复.

关于kmp算法,讲的最好的当属阮一峰的<字符串匹配的KMP算法>.一路读下来,豁然开朗.其实就是,对模式串p进行预处理,得到前后缀的部分匹配表,使得我们可以借助已知信息,算出可以右移多少位.即 kmp = 朴素匹配 + 移动多位.更多细节请看阮一峰的文章,这里就不展开了.下面给出python的代码实现.

Python实现优先级队列结构的方法详解 最简单的实现一个队列至少满足2个方法,put和get.借助最小堆来实现.这里按"值越大优先级越高"的顺序.#coding=utf-8fromheapqimportheappush,heappopclassPriorityQueue:def_

详解Python中的__new__、__init__、__call__三个特殊方法 __new__:对象的创建,是一个静态方法,第一个参数是cls。(想想也是,不可能是self,对象还没创建,哪来的self)__init__:对象的初始化,是一个实例方法

实例解析Python中的__new__特殊方法 __new__方法是什么?如果将类比喻为工厂,那么__init__()方法则是该工厂的生产工人,__init__()方法接受的初始化参数则是生产所需原料,__init__()方法会按

标签: kmp算法理解

本文链接地址:https://www.jiuchutong.com/biancheng/386939.html 转载请保留说明!

上一篇:Python缩进和冒号详解(python 代码缩进)

下一篇:Python实现优先级队列结构的方法详解(python优先级顺序)

  • 支付宝如何缴纳车辆购置税
  • 固定资产盘盈影响所有者权益吗
  • 新准则金融资产科目名称
  • 报税中反写是什么意思
  • 费用类科目分类怎么避免出错
  • 支付土地使用权的会计处理
  • 应收票据主要包括
  • 购买房产怎么确认收入
  • 材料已入库后收货怎么写
  • 公司没有设年终奖要报税吗
  • 跨地区经营建筑企业预缴增值税可以先开票后预缴吗
  • 物流公司开票税率
  • 价外费用的会计和税务处理
  • 代订住宿费可以开专票吗
  • 自然人个人能否纳税
  • bios设置技巧
  • 企业增资需要缴纳什么税
  • Secure Boot什么意思?BIOS中Secure Boot灰色无法更改解决方法详解
  • 公司补缴印花税的后果
  • 预付款退还的法律规定
  • 预付账款属于资产性质的账户
  • 以前年度进项税额转出会计分录怎么做
  • 微商行业代理奖金如何入账
  • 商业承兑汇票到期兑现流程
  • php html5
  • php随机生成1到3的数字
  • 利用php计算1+2+3+...+100
  • 异地银行结算账户的特点
  • LangChain Agent 执行过程解析 OpenAI
  • 前端请求方式
  • 利润的构成要素包括
  • php实现邮箱验证码
  • php用正则匹配网页的logo
  • C++ Linux Web Server 面试基础篇-操作系统(四、线程通信)
  • vue3中使用gis地图
  • 联营企业分得的利润
  • 应收账款等于什么加什么
  • 小规模纳税人减按1%账务处理
  • 织梦官方网站
  • 坏账准备是什么性质的科目
  • 普通发票可抵税吗
  • 小微企业报税是多久报一次
  • mysql数据查询慢
  • 医疗收费票据管理制度
  • 招待客户的住宿费发票可以报销吗
  • 上一年度所得税忘记计提了怎么办
  • 水利建设基金申报表哪里
  • 未经加工的
  • 滴滴打车开具的普通发票可以抵扣吗
  • 一般纳税人进项票是普票可以抵扣吗
  • 暂估入库成本结转
  • 增值税专用发票使用规定 最新
  • 支付给个人的劳务费需要发票吗
  • Windows Server 2008域环境下组策略两例应用
  • ubuntu无法正常开机
  • ubuntu顶部菜单栏
  • windowxp音量图标没了
  • win8设置宽带连接
  • win10正版免费升级
  • xpcpu占用100
  • win8开始界面如何设置成win7
  • ssh permission denied password
  • 关于linux中Squid代理服务器的10个实用面试问答
  • win8.1如何快速启动
  • unity加密解决方案
  • 安卓手机屏幕不好使了怎么办
  • bat删除所有文件
  • 怎么理解python
  • opengl用法
  • bat批处理文件运行不了
  • javascript简明教程
  • Jquery uploadify上传插件使用详解
  • linux中shell脚本实验总结
  • js clearInterval()方法的定义和用法
  • js清除文本框内的文字
  • centos6.5设置网络
  • 自治区地方税务局于立民简介
  • 国家税务总局江西省国家税务局
  • 稳岗补贴是否需要发放
  • 个人所得税税收完税证明哪里打印
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设