位置: 编程技术 - 正文

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

  • 未开具的增值税专用发票怎么作废
  • 按月支付劳务费开发票
  • 递延所得税负债大白话解释
  • 计提税费表格
  • 坏账准备应计入
  • 没有认证怎么办
  • 筹建期印花税退税分录
  • 宣传费属于什么税目
  • 增值税纳税申报表在哪里打印
  • 小企业会计准则调整以前年度费用分录
  • 跨区经营如何预缴税款
  • 红冲暂估原材料如何做会计分录
  • 一般纳税人出租不动产增值税税率
  • 出口收取佣金要开发票吗?
  • 投资收益所得税表怎么填
  • 专用发票丢失如何报销
  • 没有签订劳动合同员工离职怎么处理
  • 生产企业出口发票数量开错有什么影响
  • 工程施工合同暂估价格入账会计分录
  • 专门从事股权投资的合伙企业投资收益 个人所得税
  • 餐饮研发费用确认条件
  • 关于设备延期交付说明
  • 管理会计完全成本法和变动成本法例题
  • 资产负债表流动性从强到弱
  • 固定资产改扩建过程中,发生的人工费用
  • php初学
  • 公司收到医疗保障局打入的钱怎么做账
  • 怎么添加动态磁贴
  • 自查补缴增值税如何申报
  • vue使用技巧
  • PHP:imagepolygon()的用法_GD库图像处理函数
  • 2020年农业病虫害
  • 商贸公司用什么名字最好
  • php中array用法
  • mongodb4.4.2安装教程
  • 不在经营范围内经营违反了什么法
  • 允许从销项税额中扣除的有
  • 土地增值税采用
  • var文件是什么意思
  • 中餐补助
  • 借贷记账法的基本规则和账户结构
  • 非营利组织如何盈利
  • 非货币性资产含义
  • 发票没有纳税人识别号怎么重开
  • 接受捐赠的增值税怎么处理
  • 教育局可以接受捐赠吗
  • 工程材料如何管理
  • 结转后还可以改凭证吗
  • 公司美元账户收款方便吗
  • 应收票据的计价应按
  • 账实不符怎么调账
  • 机票价格分类
  • 公司提前扣员工保险合法吗
  • 报关单填制的运费怎么算
  • 事业单位收费可以收取相关服务费吗
  • 认缴制下实收资本印花税
  • mysql正则表达式匹配数字
  • xp系统玩英雄联盟出现win32
  • alp是什么文件
  • 电脑开机后显示xp界面后一直是黑屏状态
  • ubuntu14.04升级
  • win8c盘
  • w10系统怎么压缩
  • node js教程
  • rapidjson使用
  • 什么是自然数
  • Node.js中的全局对象有
  • unity 替代
  • 20行的python编程题
  • 置顶聊天的人怎么不见了
  • android 保存密码
  • jquery的实现原理
  • 郑州税务局电话客服电话
  • 企业之间无偿借款是否交税
  • 个税申报所属期和所得期
  • 河南税务申报
  • 监督医院的单位
  • 首问责任制的概念
  • 税务上的关联企业指哪些
  • 工本费每月都扣?
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设