位置: 编程技术 - 正文

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

  • 代扣代缴境外增值税可以抵扣
  • 税后利润和净利润是一样的吗
  • 土地出让金会涨价吗
  • 公立医院事业单位录用是编制吗
  • 公司注册后一直没有营业怎么办
  • 建筑企业的成本
  • 核定征收需要什么条件
  • 购入股票作为短期投资是什么凭证
  • 速达3000货品怎么入库
  • 2019一般纳税人新政策
  • 资产入股会计处理
  • 生产企业出口转内销增值税申报
  • 如何区分总额法和净额法
  • 国际贸易公司注册需要什么条件海南
  • 往年预付账款错了,应如何调?
  • 多付车款退回怎么做账
  • 应付汇差是什么意思
  • 工程项目立项前包括哪几个过程
  • 以前年度留抵用完 不能抵欠税
  • 收取线路维护费合法吗
  • 二房东税务局开发票
  • 本期免税收入是什么
  • 应收票据的核算内容及其贴现
  • 经营资产和金融资产有哪些
  • window10总是自动开机
  • 公司修建污水池申请书
  • 销售过程会计核算实训过程
  • 部门活动经费怎么算
  • 差旅费报销管理规定2022
  • 企业的生产成本等于
  • vue url 参数
  • 回迁安置房是否有产权
  • php yield 异步
  • 史密斯理工学院
  • PHP使用http_build_query()构造URL字符串的方法
  • pytorch csdn
  • 纳税人提供技术开发服务
  • 期货收入交个人所得税吗
  • python怎么写文字
  • 关于录制初三毕业班家长寄语通知
  • 管理人员工资结构图
  • 订单不足停工
  • 个人所得税0申报什么意思
  • 受托方代扣代缴增值税、消费税的纳税人
  • 实收资本没有实缴,财务报表里面怎么写
  • 合作经营利润分配协议
  • 收到社保局的稳岗通知
  • 小规模增值税减免
  • 预收账款属于借还是贷
  • 跨年成本少结转如何调整
  • 如何冲其他应付款发票
  • 进项发票认证多了留抵多久
  • 房屋租赁费交什么税
  • 建账前应考虑什么问题
  • sql存储过程实例有哪些
  • sql语句学习
  • sqlserver代理服务启动失败
  • 备份数据还原不了怎么办
  • mac的qq缓存在哪里怎么打开
  • logo是什么文件夹
  • win8搜索程序和文件在哪里
  • linux系统ftp服务
  • win7右下角点击没反应
  • suse linux教程
  • Win7旗舰版系统镜像文件
  • win10系统打不开应用程序
  • win10系统创建一个快捷bat
  • 电脑cf截图保存在哪里
  • ExtJS如何设置与获取radio控件的选取状态
  • jquery实现简洁文件上传表单样式
  • opengl入门教程
  • nodejs mysql库
  • shell脚本引用文件
  • unity3d winform
  • js 实现复制到粘贴功能
  • 东城国税局局长
  • 医院网上预约号怎么取消
  • 深圳增值税勾选平台网址
  • 种子在什么情况下能发芽
  • 房地产的土地增值税怎么交
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设