KMP算法笔记
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法笔记,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1082字,纯文字阅读大概需要2分钟。
内容图文
![KMP算法笔记](/upload/InfoBanner/zyjiaocheng/645/88a06a5eabae4c7da965c87ed5344a0c.jpg)
简介
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。
核心思路
假设字符串 a s d d s s d f d s d f d f s , 想要匹配字符串 s d f d s;
拿到字符串,对每个字符做区分,分为: s, sd, sdf,sdfd,sdfds
找到每个字符串的 前缀与后缀相等的最大长度: (例:sdfd: s d f d 为1 , sdfds: s d f d s 为2)
s:0,sd:0,sdf:0,sdfd:1,sdfds:2
原字符串 a s d d s s d f d s d f d f s,
索引 0 1 2 3 4
目标字符串 s d f d s
maxL 0 0 0 1 2
nextL -1 0 0 1 2
此时,可以去掉maxL,并对目标字符串与原字符串从第0个字符进行匹配
原字符串 a s d d s s d f d s d f d f s,
索引 0 1 2 3 4
目标字符串 s d f d s
nextL -1 0 0 1 2
当匹配不正确时,nextL为-1则整体向右移动1格;nextL为其他数字,则索引的数字及对应的字符移动到nextL中与索引相同的数字的位置
wxy951218 发布了2 篇原创文章 · 获赞 0 · 访问量 156 私信 关注内容总结
以上是互联网集市为您收集整理的KMP算法笔记全部内容,希望文章能够帮你解决KMP算法笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。