赞
踩
目录
参考书籍【数据结构C语言版第2版-严蔚敏版】
KMP 是由 Knuth 、 Morris 和 Pratt 同时设计实现的,它是用来串匹配的。比如:在搜索引擎、拼写检查中等应用中都需要用到串匹配。
串的模式匹配设有两个字符串S和T, 设S为主串,也称正文串;设T为子串,也称为模式。 在主串S中查找与模式T相匹配的子串,如果匹配成功, 确定相匹配的子串中的第一个字符在主 串S中出现的位置。
通常串匹配有俩种方法:BF(暴力法)、KMP算法
在讲 KMP 算法之前,先简单了解一下暴力法如何实现,方便作对比,理解更加透彻
暴力法顾名思义,就是通过循环一个个字符进行比较,相等比较下一个,不相等回溯指针重新比较,这也是比较笨且有效的方法。下面看看暴力法如何实现。
提前说明:以下俩种算法指针均使用 i 和 j,并从下标 1 开始
【算法步骤】
【案例演示】
S= "ababcabcacbab" T= "abcac"
不相等时,i指针回溯公式:(i-j+2),比如第一趟中: (i-j+2)= (3-3+2)=2,第二趟 i 从 第 二个字符开始
【附上代码】
- // src 主串,dest 子串
- public static int bf(String src, String dest) {
- int i = 1;
- int j = 1;
- while (i <= src.length() && j <= dest.length()) {
- if (src.charAt(i - 1) == dest.charAt(j - 1)) {
- // 匹配成功则向后移
- i++;
- j++;
- } else {
- // 匹配失败,回溯i和j
- i = i - j + 2;
- j = 1;
- }
- }
-
- if (j > dest.length()) {
- // 全部匹配成功
- return i-dest.length();
- }else {
- // 匹配失败
- return -1;
- }
- }
BF算法思路直观简明。, 但当主串匹配失败时 指针 i 总是回溯到 i-j+2 位置, 模式串的 指针总是恢复到首字符位置 j= 1, 因此, 算法时间复杂度高。
下面讲解的 KMP 算法正是改变 i 和 j 指针的回溯位置 从而提高效率。
KMP 算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的,相较于BF算法,其改进在于,当字符不相等时,不需要回溯 i 指针,j 指针则是利用 "部分匹配值" 回溯到有效的位置上。
从下面的例子看一下,KMP算法究竟比BF算法快在哪。
回顾上面BF算法的图解,第三趟中 i =7,j = 5 不相等时,如图所示:
按照BF算法, 又会从 i =4,j =1 开始比较。但是在 KMP 算法中,i 的位置不变,而 j 则按照 "部分匹配值" 进行回溯。
在上图中可以发现,i=4,j=1,和 i=5,j=1,以及 i=6,j=1, 这三次比较是没有必要的,因为我们在上一趟中就能确定主串中第4、5、6位置的字符就是 'b','c', 'a'。 子串第一个字符是 'a'。 因此我们直接跳过这三次的比较,将模式串向右滑动三个字符,直接从 i = 7,j=2 开始比较。
通过对比可以看出,当俩个字符 '失配' 时,KMP 算法确实要比 BF 算法有更少的比较,接下来探讨 KMP算法是如何实现的。
在上面的示例中可以发现,KMP 算法最关键的在于 j 指针的移动,当俩个字符 '失配' 时,j 不会从 1 在重新比较,而是按照某种 '规则' 移动,这种规则是什么呢? 下面开始研究:
在上面的示例中我们仔细观察一下,j 由原来的 5 指向 了2,第一个 'a' 移动到 第二个 'a' 的位置上,假设我们用 k 表示 j 要移动的位置,则k=2,如图所示:
在上图中那么我们可以看出来存在一个规律:模式串中 k 的前 1~k-1 个字符与 j-k+1~j-1 个字符存在公共的前后缀
用公式表示为:
公共前后缀补充:
假设有字符串 S = "ABAAB"
S的前缀:['A']、['AB']、['ABA']、['ABAA']
S的后缀:['B']、['AB']、['AAB']、['BAAB']
S的公共前后缀为:['AB']
再看一个例子:
1、下面 i = 5 与 j =5 比较不相等时, 可以发现 j -1 前面的子串中仍然含有公共的前后缀 'AB' ,此时应该如何移动呢?
2、没错,只需要将模式串中 j-1 的前缀放到后缀的位置上。 j 由原来的 6 变成了 3,则k=3
3、此时 i = 6,j=3 仍然不相等,但是 j 前面的子串 'AB' 没有公共的前后缀了,因此 j 只能从第一个字符重新开始比较。
通过以上俩个示例,得出三个结论:
① k 表示当俩个字符 '失配' 时,j 指针要回溯的位置
② k 的计算方式为; 模式串前 j-1 子串的最大公共前后缀的长度 + 1。
③ k 的值只和模式串有关系,和主串无关
还需要注意一点,每次移动的 j 指针都可能进行回溯,因此需要保存每一个 j 对应的 k,通常用一个数组来保存 k 的值,表达公式为:
next [j] = k
next[j] 表明当俩个字符 '失配' 时, j 指针需要回溯的位置,由此可以引出 next[j] 函数的定义:
公式非常重要,这是求解next数组的核心!!!!!
下面通过一个案例演示 next[j] 的求解过程:
T = "ABABA" 找出该模式串的 next[j]
(1)j = 1 时,next[1] =0
(2)j = 2, j-1 子串 'A' 没有公共的前后缀,next[2] = 1
j=3,j-1 子串 'AB' 没有公共的前后缀,next[3] = 1
(3)j =4 , j-1 子串 'ABA', 存在公共前后缀为:'A' , 因此 next[j] = 2【时刻谨记 k 的值为:j-1子串的最大公共前后缀+1】
(4)j=5,j-1子串 'ABAB' ,存在公共前后缀 'AB' , 因此 next[j] = 3
【附上代码】
- public static int[] getNext(String dest) {
- // 将dest转换为字符数组,方便操作
- char[] ch = dest.toCharArray();
- // 由于我们从下标为1开始,因此长度要+1,避免下标越界
- int[] next = new int[ ch.length+1];
- next[1] = 0;
- int j = 1, k = 0;
- while (j < ch.length) {
- if (k == 0 || ch[j-1] == ch[k-1]) next[++j] = ++k;
- else k = next[k];
- }
- return next;
- }
看完代码,估计很多人和我一开始一样的想法,求解next数组的流程我是清楚了,但是这代码是什么鬼? while 循环里的操作是啥意思?这俩段代码起初看的我是云里雾里~~现在我将我的理解和大家分享一下:
假设当前已经知道 next[j] = k,这表明在模式串中存在以下关系:
想要求得 next[ j+1 ] = ? , 无非就有俩种情况,对应代码中的 if --else:
① 的情况,如图所示:通过图中可以看出 ,next[j+1] = next[j] + 1 == next[j+1] = k + 1 因为要循环处理进而转换为:next[++j] = ++k
② , 这种情况要复杂一些,这里我引用书中的俩句话:
我们可以把整个模式串想象成俩个串,就是分成俩部分,k后面的看做是主串,k 前面的看做模式串,将模式串与主串进行匹配。
话不多说,直接看图:
上图中,,将模式串移动到 next[k] 的位置上 继续和 第 j 个字符相比较。如下图所示:
此时 k = next[k] , 这是因为我们通过 next[] 数组将 k 移动到了 next[k] 的位置,因此 k = next[k]
再看现在的情况,,这不就回到了第一种情况了吗。因此我们可以说当 时,是通过 k = next[k] 来调整 k 的位置 与 j 进行比较
那么可能会有兄弟来问了,那他要一直 怎么办?
这种情况,代码中也考虑到了,如果一直不相等,则 k 的值 最后肯定会指向 0 ,而在 if 语句里,也将这个条件加了进去,也就是说最后 next[j+1] = 1
求得了 next[j] 数组,演示一遍 KMP 算法的完成流程:
S = "ABABCABABAC" T = "ABABA", 模式串的 next[j] 在上面已经求得。
1、i=5,j =5 发现俩个字符不一致, 此时 i 指针保持不变,在 next 数组中查看 A 的回溯位置 next[5] = 3,将 j 指针回溯到 3 的位置上
2、j 移动到第三个位置后,i =5 ,j=3 仍然不相等,next[3] = 1, 将 j 回溯到第一个位置
3、j 回溯到第一个位置后,仍然不相等,但是 j 已经回溯到首位了,next [1] = 0 无法在移动了,因此 i 向后移 一位。
4、此时比较完毕,返回模式串第一次出现在主串的位置: i - T.length
【KMP算法代码】
- public static int kmp(String src, String dest) {
- int[] next = getNext(dest);
- int i = 1;
- int j = 1;
- while (i <= src.length() && j <= dest.length()) {
- if (j == 0 || src.charAt(i - 1) == dest.charAt(j - 1)) {
- // 匹配成功则向后移
- i++;
- j++;
- } else {
- // 匹配失败,不在回溯i指针
- // i = i - j + 2;
- // j指针根据next数组回溯
- j = next[j];
- }
- }
-
- if (j > dest.length()) {
- // 全部匹配成功
- return i-dest.length();
- }else {
- // 匹配失败
- return -1;
- }
- }
以上是我对KMP算法的了解,如有纰漏还请各位兄弟指出~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。