34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.pdf
《34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.pdf》由会员分享,可在线阅读,更多相关《34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.pdf(16页珍藏版)》请在三一文库上搜索。
1、34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? 上一节我们讲了BM算法,尽管它很复杂,也不好理解,但却是工程中非常常用的一种高效字符串匹配算法。有统计说,它是最高效、最常用的字符串匹配算法。 不过,在所有的字符串匹配算法里,要说最知名的一种的话,那就非KMP算法莫属。很多时候,提到字符串匹配,我们首先想到的就是KMP算法。 尽管在实际的开发
2、中,我们几乎不大可能自己亲手实现一个KMP算法。但是,学习这个算法的思想,作为让你开拓眼界、锻炼下逻辑思维,也是极好的,所以我 觉得有必要拿出来给你讲一讲。不过,KMP算法是出了名的不好懂。我会尽力把它讲清楚,但是你自己也要多动动脑子。 实际上,KMP算法跟BM算法的本质是一样的。上一节,我们讲了好后缀和坏字符规则,今天,我们就看下,如何借助上一节BM算法的讲解思路,让你能更好地 理解KMP算法? KMP算法基本原理 KMP算法是根据三位作者(D.E.Knuth,J.H.Morris和V.R.Pratt)的名字来命名的,算法的全称是Knuth Morris Pratt算法,简称为KMP算法。
3、KMP算法的核心思想,跟上一节讲的BM算法非常相近。我们假设主串是a,模式串是b。在模式串与主串匹配的过程中,当遇到不可匹配的字符的时候,我们希望 找到一些规律,可以将模式串往后多滑动几位,跳过那些肯定不会匹配的情况。 还记得我们上一节讲到的好后缀和坏字符吗?这里我们可以类比一下,在模式串和主串匹配的过程中,把不能匹配的那个字符仍然叫作坏字符,把已经匹配的 那段字符串叫作好前缀。 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/
4、15 15:36:14 当遇到坏字符的时候,我们就要把模式串往后滑动,在滑动的过程中,只要模式串和好前缀有上下重合,前面几个字符的比较,就相当于拿好前缀的后缀子串, 跟模式串的前缀子串在比较。这个比较的过程能否更高效了呢?可以不用一个字符一个字符地比较了吗? 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 KMP算法就是在试图寻找一种规律:在模式串和主串匹配的过程中,当遇到坏字符后,对于已经比对过的好前缀
5、,能否找到一种规律,将模式串一次性滑动很多 位? 我们只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是v,长度是k。我们把 模式串一次性往后滑动j-k位,相当于,每次遇到坏字符的时候,我们就把j更新为k,i不变,然后继续比较。 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 为了表述起来方便,我把好前缀的所有后缀子串中,最长的可匹配前缀子
6、串的那个后缀子串,叫作最长可匹配后缀子串;对应的前缀子串,叫作最长可匹配前缀 子串。 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 如何来求好前缀的最长可匹配前缀和后
7、缀子串呢?我发现,这个问题其实不涉及主串,只需要通过模式串本身就能求解。所以,我就在想,能不能事先预处理计 算好,在模式串和主串匹配的过程中,直接拿过来就用呢? 类似BM算法中的bc、suffix、prefix数组,KMP算法也可以提前构建一个数组,用来存储模式串中每个前缀(这些前缀都有可能是好前缀)的最长可匹配前缀子串 的结尾字符下标。我们把这个数组定义为next数组,很多书中还给这个数组起了一个名字,叫失效函数(failure function)。 数组的下标是每个前缀结尾字符下标,数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。这句话有点拗口,我举了一个例子,你一看应该就懂了。
8、34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 有了next数组,我们很容易就可以实现KMP算法了。我先假设next数组已经计算好了,先给出KMP算法的框架代码。 / a, b分别是主串和模式串;n, m分别是主串和模式串的长度。 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松
9、理解KMP算法?.html2019/1/15 15:36:14 public static int kmp(char a, int n, char b, int m) int next = getNexts(b, m); int j = 0; for (int i = 0; i 0 if (ai = bj) +j; if (j = m) / 找到匹配模式串的了 return i - m + 1; return -1; 失效函数计算方法 KMP算法的基本原理讲完了,我们现在来看最复杂的部分,也就是next数组是如何计算出来的? 当然,我们可以用非常笨的方法,比如要计算下面这个模式串b的next4
10、,我们就把b0, 4的所有后缀子串,从长到短找出来,依次看看,是否能跟模式串的前缀 子串匹配。很显然,这个方法也可以计算得到next数组,但是效率非常低。有没有更加高效的方法呢? 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 这里的处理非常有技巧,类似于动态规划。不过,动态规划我们在后面才会讲到,所以,我这里换种方法解释,也能让你听懂。 我们按照下标从小到大,依次计算next数组的值。当我们要计算nex
11、ti的时候,前面的next0,next1,nexti-1应该已经计算出来了。利用已经计算出来 的next值,我们是否可以快速推导出nexti的值呢? 如果nexti-1=k-1,也就是说,子串b0, k-1是b0, i-1的最长可匹配前缀子串。如果子串b0, k-1的下一个字符bk,与b0, i-1的下一个字符bi匹配,那子串b0, 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 k就是b0, i的最长可
12、匹配前缀子串。所以,nexti等于k。但是,如果b0, k-1的下一字符bk跟b0, i-1的下一个字符bi不相等呢?这个时候就不能简单地通 过nexti-1得到nexti了。这个时候该怎么办呢? 我们假设b0, i的最长可匹配后缀子串是br, i。如果我们把最后一个字符去掉,那br, i-1肯定是b0, i-1的可匹配后缀子串,但不一定是最长可匹配后缀子串。所 以,既然b0, i-1最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于bi,那么我们就可以考察b0, i-1的次长可匹配后缀子串bx, i-1对应的可匹 配前缀子串b0, i-1-x的下一个字符bi-x是否等于bi。如果等
13、于,那bx, i就是b0, i的最长可匹配后缀子串。 34|字符串匹配基础(下):如何借助BM算法轻松理解KMP算法? file:/F/temp/geektime/数据结构与算法之美/34字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?.html2019/1/15 15:36:14 可是,如何求得b0, i-1的次长可匹配后缀子串呢?次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中,而最长可匹配后缀子串又对应最长可匹配前缀子 串b0, y。于是,查找b0, i-1的次长可匹配后缀子串,这个问题就变成,查找b0, y的最长匹配后缀子串的问题了。 34|字符串匹配基础(下):如何借助B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 34 字符串 匹配 基础 如何 借助 BM 算法 轻松 理解 KMP
链接地址:https://www.31doc.com/p-5529917.html