For investors
股价:
5.36 美元 %
认识达内从这里开始
认真做教育 专心促就业
每一本《数据结构》方面的书应该都会讲 KMP 算法， KMP 算法可以说是知名度非常高的算法之一，为什么会叫做 K MP 算法?是因为 KMP 是由三位大牛： D.E.Knuth 、 J.H.Morris 和 V.R.Pratt 几乎同时发现的。所以取了每个人的第一个字母叫做 K MP 算法。
问题描述
给你一个母串和一个子串;请在母串中寻找子串如果母串中存在子串则返回 T rue ，不存在则返回 F alse 。
示例：母串： ababababcabc ，子串： abababca
输入： ababababcabc
abababca
输出： True
解决方案
如 K MP 算法的时间复杂度为 O ( m+n )比暴力破解的时间复杂度 O ( m*n )小很多，这是因为在 K MP 算法中子串和母串不匹配的时候不会将子串向右挪移 1 位，而是将子串向后挪移 k 位。
如何确定子串向后挪移的位数呢?这个就像需要建立 next 数组来进行匹配， next 数组就是子串中每一个位置的最大公共长度。最大公共长度在算法导论里面就被记为 next 数组。
计算 next 数组就是计算子串中每一个位置的最大公共长度。简单来说可以理解为遮住这个元素，去查看这个元素前面的相同前缀和后缀的长度，这个长度就是该元素对应的值，如图。
确定 next 数组后我们就可以开始子串与母串的匹配，当匹配到的元素值不同时，查找子串中该元素对应的 next 值，根据 next 值来确定子串该如何移动，移动后再开始新一次的匹配，一直循环这个过程直到匹配结束。
结语
KMP 算法的核心就是在于 next 数组的建立，建立正确的 next 数组至关重要，通过 next 数组里面的 next 值可以帮助我们有效的减少循环次数和节约大量的时间。
达内免费试听课程火热报名中，带你轻松入行，26大课程全国45个城市，129家中心均可就近学习，学完后，达内老师会帮助进行面试辅导，在面试前，就带你跨过可能存在的坑，让你入职更加顺利
【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请添加3216764521学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。
< 上一篇：java软件开发工程师的常用算法
下一篇：东莞达内分享提升UI设计效果的6个小技巧 >
2023-08-11
免费试听课程
- 全部课程
- IT课程
- 设计课程
- 运营课程
4578
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 哈尔滨
- 济南
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 长沙
- 昆明
- 太原
- 无锡
- 石家庄
- 南宁
- 佛山
- 珠海
- 宁波
- 保定
- 呼和浩特
- 洛阳
- 烟台
- 运城
- 潍坊
- 开课名称
- 开班时间
- 抢座
- 咨询
- 开课名称
- 开班时间
- 抢座
- 咨询
-
- Java全链路开发
- 11月27日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 11月27日
- 火热抢座中
- 立即咨询
- 人工智能工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 11月27日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 11月27日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 11月27日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 11月27日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 11月27日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 11月27日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 11月27日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 11月27日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 11月27日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 11月27日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 11月27日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 11月27日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 11月27日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 11月27日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 11月27日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 11月27日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 11月27日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 11月27日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 11月27日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 11月27日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 11月27日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 11月27日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 11月27日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 11月27日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 11月27日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 11月27日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 11月27日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 11月27日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 11月27日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 11月27日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 11月27日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 11月27日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 11月27日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 11月27日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 11月27日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 11月27日
- 火热抢座中
- 立即咨询
预约申请试听课
开设课程
开课城市
友情链接
Copyright © 2024 Tedu.cn All Rights Reserved 京ICP备08000853号-56 京公网安备 11010802029508号达内时代科技集团有限公司 版权所有
注：学员信息+企业信息均来自达内教育内部CRM系统真实统计，非宣传使用。
课程适用人群：成人
400-996-5531
lihm@tedu.cn
