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)
|