一:KMP算法与BF算法的区别与特点
1.KMP算法和BF算法的定义
1.KMP算法:
KMP算法是一种改进的字符串匹配算法KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next数组实现，数组本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
2.BF算法:
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，
BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，
若相等，则继续比较S的第二个字符和 T的第二个字符；
若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。
BF算法是一种暴力算法。
2.KMP算法和BF算法的区别
KMP和BF唯一不一样的地方在于:
KMP算法中的主串的i并不会回退,并且j也不会移动到0号位置
此时主串跟子串匹配失败,
如果是BF算法的话,i会回退到下标1的位置,j会回退到下标0的位置再次进行匹配
如果是KMP算法的话,i不会回退,只有j会回退,我们会感到惊讶,怎么做到的啊?
我们先通过肉眼观察一下,
那么我们如何在主串中找到和子串匹配的一部分串呢?
这里就需要用到next数组了
二:next数组的求解
1.next数组求法(理论):
next数组的作用:
保存子串某个位置匹配失败后回退的位置
定义:
next[j]=k;
如果j下标匹配失败时,那么下次匹配时j回退到下标为k的位置
手求next数组:
而k的值是这样求的:
1:找到匹配成功部分的两个相等的真子串(不包含本身),一个以下标0开始,另一个以下标j-1结尾.
2:不管怎样都有:next[0]=-1;next[1]=0;
next数组也可以从0开始,也就是next[0]=0;
只需把我们上面那种形式所求出的next数组中的值全部加1即可
2.next数组求法(实操):
下面我们演示一下next数组的求法
3.求next数组练习题:
下面是两个例子,大家可以先做一下,巩固巩固,我们还要从这两个例子中再说明一些重要的点
友情提醒:
- 两个相等的串:第一个串必须从0下标处开始
- 第二个串必须从j-1下标处结尾
- next数组的两个相同子串是可以重合的
1.
“ababcabcdabcde”,求next数组
2.
“abcabcabcabcdabcde”,求next数组
3.练习题总结
通过这两个题,我们可以发现:
1.next数组不可能跳着加!!!,所以,如果你求出来的next数组有跳着加的现象,那证明你做错了
2.也就是说next数组满足若next[j]=k,p[j]==p[k],那么next[j+1]=k+1;(p是子串)
