位置: 编程技术 - 正文

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优先级顺序)

  • 增值税明细账用三栏式还是多栏式
  • 税款已缴未入库是怎么回事
  • 出差补贴需要交税
  • 等额本息还款的特点
  • 企业递延所得税费用的计算公式
  • 工资发放凭证由谁出具
  • 企业所得税计税金额怎么算
  • 借款利息支出账务处理
  • 农产品增值税抵扣新政策2021
  • 预付货款工程完工后如何结转?
  • 营业费用率说明什么
  • 支付各种办公费用
  • 税务局代增值税专用发票盖什么章
  • 开物流公司能挣多少钱
  • 转让集体土地所有权
  • 简易征收货物的运费
  • 非居民企业能否认定为一般纳税人
  • 288000元大写怎么写
  • 增值税纳税申报表在哪里打印
  • 购买土地建厂房还要交土地使用费吗
  • 公司转让税费如何计算
  • 个体工商户减免房租政策2022年
  • 应收和预收可以抵消吗
  • 补领以前月份的工资如何计算个人所得税?
  • 工程承包付款最佳方式
  • 可抵扣的金税盘维护费会计分录怎么做?
  • 自建厂房转固定资产如何办理手续
  • 在建工程工程款优先受偿权
  • 2021年8月现在还能去武汉吗
  • php数组根据值排序
  • win10右键失灵解决办法
  • 小规模纳税人多少钱不用交税
  • 折扣销售的定义
  • 梅德威海滩棕榈树间散步的冲浪者,印尼巴厘岛 (© helivideo/GettyImages)
  • 部署文档
  • laravel 分层
  • 上月未结账本月不能操作任何业务
  • 出口货物的出口日期以
  • php如何生成html
  • 冲销进项税
  • 华为od机试成绩什么时候出来
  • opencv 边缘
  • unplugin-auto-import github
  • php页面跳转可以用header
  • 销售折扣购物卡怎么做账
  • 财务软件服务合同要交印花税吗
  • 社保断交一个月但是后面正常缴费
  • 哪些合同必须签订书面合同
  • 公交卡充值发票报销单怎么填
  • 一般纳税人只有销项没有进项
  • 禁止DedeCMS未审核文档支持动态浏览方法
  • php 文件处理
  • 小微企业缴纳增值税的账务处理
  • sql server2003
  • 垃圾处理费申报怎么填
  • 残保金会计分录人员经费
  • 以前年度多缴纳房产税,可以递延次年度使用么
  • 土地增值税是什么税种类型
  • 生产成本与管理企业经营实战感想
  • 公司注册资金抽走违法吗
  • 个人所得税多计算了一个月工资怎么办
  • 增资扩股对原股东的影响
  • 对方要求先开发票怎么办
  • 建筑业人工费怎么做账
  • 商品库存明细账
  • win8系统蓝屏后无法修复
  • 电脑右下角windows设置在哪
  • 教你彻底消灭牛身上的蜱虫
  • os x10.11el capitan beta6更新了什么?os x10.11el capitan beta6发布下载
  • centos7添加ip地址
  • sistray.exe - sistray是什么进程 有什么用
  • win8.1开始菜单改win7
  • Win10手机版校
  • webrtc opus
  • python下载百度云文件
  • linux pymol
  • python多线程例子
  • android中fragment
  • 电子税务局申领的发票怎么读入
  • 国际税务师证书
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设