|
1.概述.
快速模式匹配算法，简称 KMP 算法，是在 BF 算法基础上改进得到的算法。 BF 算的实现过程就是 "傻瓜式" 地用模式串（假定为子串的串）与主串中的字符一一匹配，算法执行效率不高，所以为了减少算法的时间复杂度，特引出KMP算法
2.基本原理
example:
由此可以看出，每次匹配失败后模式串移动的距离不一定是 1，某些情况下一次可移动多个位置，这就是 KMP 模式匹配算法
模式串移动距离的判断：
每次模式匹配失败后，计算模式串向后移动的距离是 KMP 算法中的核心部分。
其实，匹配失败后模式串移动的距离和主串没有关系，只与模式串本身有关系。
给每个模式串配备一个数组（例如 next[]），用于存储模式串中每个字符对应指针 j 重定向的位置（也就是存储模式串的数组下标），比如 j=4，则该字符匹配失败后指针 j 指向模式串中第4 个字符
3.实现 next 数组的 C 语言代码：
4.next 数组的缺陷及改进
当匹配失败时，Next 函数 开始继续进行模式匹配，但是从图中可以看到，这样做是没有必要的，纯属浪费时间
出现这种多余的操作，问题在当 T[i-1]==T[j-1] 成立时，没有继续对 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判断。改进后的 Next 函数如下所示：
5.KMP的实现：附件
KMP算法C源码.rar
(1.18 KB, 售价: 1 E币)
【必读】版权免责声明
1、本主题所有言论和内容纯属会员个人意见，与本论坛立场无关。2、本站对所发内容真实性、客观性、可用性不做任何保证也不负任何责任，网友之间仅出于学习目的进行交流。3、对提供的数字内容不拥有任何权利，其版权归原著者拥有。请勿将该数字内容进行商业交易、转载等行为，该内容只为学习所提供，使用后发生的一切问题与本站无关。 4、本网站不保证本站提供的下载资源的准确性、安全性和完整性;同时本网站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。 5、本网站所有软件和资料均为网友推荐收集整理而来，仅供学习用途使用，请务必下载后两小时内删除，禁止商用。6、如有侵犯你版权的，请及时联系我们（电子邮箱1370723259@qq.com）指出，本站将立即改正。
| 
