|
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的实现：附件
cKMP算法.rar
(1.18 KB, 下载次数: 12)
| 
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
