00:02
同学们,我们来看一下KMP算法的一个介绍,首先我们了解一下KKP算法是一个什么样的算法,它是一个解决模式串,在文本串中是否出现过,如果出现过最早出现的位置的经典算法,那么这个字符它也叫字符串查找算法,简称KP算法。为什么叫KMP呢?这是在于哈,这个算法呢,是由这三个人他们联合发表,然后呢,就以他们的姓名姓氏啊姓氏命名来来的,你看第一个人他里面有个K对不对,第二个人里面有个什么呢?有有一个P,看到没有,下面还有一个人有个M,因此呢,KP就这么来的。那这个算法其实并不是说呃一个一个,就是说好像好像是个很新的一个算法,其实在1977年呢,他就已经把这个算法提出来了,这个Kim密算法呢,它是利用之前判断过的信息,通过一个nextx数组,也就是说求这个next数组。
01:08
这个代数组是什么呢?是叫部分,叫部分搜索词,这个数组呢。很关键,这个求出这个数组很关键,通过这个next数组呢,保存模式串中前后最长公共子序列的程度。这个怎么求出最最长公共子序列的长度,这个很关键。待会呢,我们会详细说这个事情,每次回溯时通过那数组找到前面匹配过的位置,省去了大量的计算时间。关于KP的算法呢,就说如果说要彻底的了解,还是有一定有一定难度的。那么网上有一篇文章,我觉得写的比较细致,可以大家参考一下,给家看一下,这篇文章呢,是比较详细的阐述了这个KP算法是怎么来的。
02:02
OK,他讲的比较细致啊,甚至还提到了有限状态自动机这样一些东西,很详细很全,但是有时候讲的过于详细吧,你有时候也会觉得不是那么好理解。总而言之,这个呢,这篇文章已经写的非常的细致了,如果同学们想彻底的非常清晰的搞懂这一个KP算法呢,可以参考一下这篇文章,好吧,那我呢,在讲的时候可能就不会讲这么细致了。那么我会直接把最。精髓最重要的那一部分给大家讲清楚,而且能够大家可以做到什么呢?一一个是你是理解KB算法了,第二个呢,你能够就是在笔试或者面试的时候呢,你能够把它的原理以及代码写出来就可以了,我的关键点是放在一个是原理,第二个呢,就是能够把代码给你们敲出来,你们也能够照着老师思路把代码写出来,代码其实没有几行。
03:02
但理解这个过程它比较它比较绕,OK,好,那这篇文章我就推荐给大家好吧,大家到时在我的这个幻灯片里面呢,也会有这一个地址。好,那么我们就以一个具体的案例来说这个KP算法它到底是怎么来实现的?来吧,首先我们先看这个是一个案例,这有个字符串。我就不去念它了,还有一个指串是这个串我也不去念了,现在判断S1中STRING1中就STRING1,就这个原串里面有没有包含属性二,如果有呢,返回它的第一次出现的位置,如果没有返回复一,这个时候我们要求用偏P算法完成,不要使用简单的暴力匹配。那关于这个思路,我这里有一篇文章,我这里已经总结出来了一个图解,大家跟上我的思路来看一看就可以了,好吧。来跟上老师的思路。我一边讲呢,一边给大家做相相应的这个解释,这有个串,这有个指串。
04:06
首先第一步是不是还是按照我们的。套路,假设这边有一个I,假定有个I啊,这边有个结,是不是先让A和B比较,显然这个不匹配,不匹配会怎么样呢?同学们,不匹配你,你想你会怎么样,你是不是会让这个会让这个I往后面移动一下呀,是不是解这个位置不动吗?因为你第一个都没匹配上,你动啥呀,于是就出现了后移。这个注意啊,这个时候子串并没有后移,它还是A,它和我们的这一个圆串,就是我们STRING1的B比较,还是没有找到,于是继续后移,继续后移呢。呃,继续会议,相当于说A就应该到A和C去比了,但是还是比比比较不到最后一直重复,直到STRING1中有一个字符跟STRING2的第一个字符从符合位置,也就是说到哪一步了呢?到这一步就A和我们只串的A和这个原串的A这匹配上了,匹配上以后呢,接着比较好,下面就比较简单,就比较B比较C,比较B比较A比较B,诶就就这样子的,诶。
05:13
各位大家看一下,就是这样依次比就行了,比比比好,这个时候当比到D。和这个空格的时候就出现了一个问题,大家接着往下看。下面看啊,我们匹配到这了,那匹配到这个地方的时候,也就是下面这句话很关键的地方了,同学们注意听讲。这时想继续匹配。便利是锐意的下一步,这时这个时候大家想好。这个时候。我们的子串地匹配到原创的空格了,如果按照暴力匹配,就会出现这样一个情况。干什么呢?让。让这个A。跟这个B匹配,因为你刚才是跟A匹配上的嘛,现在是不是又出现这个情况了。但是这样想,如果这样匹配,我们又回到了。
06:02
暴力匹配的那种思路是错的,那么我们来看这里面分析啊,这是我们想到是继续遍历十中一的下一个,下一个字符,也就是B,也就是B,那么重复第一步,其实这是不明智的,因为此时BCD已经比较过了,没有必要再做重复的工作。这个句话其实很多人是不太明白的,为什么叫BCD已经比较过了呢?我给大家讲一下啊,我先把这个话念完再给大家讲,大家不着急,为什么说BCD已经比较过了啊,待会再再说这个话。一个基本的事实是,当空格与D不匹配的时候,你其实知道前面的六个字符是ABCDAB,是不是ABCDAB啊,天MP算法的思想是设设法利用这个已知信息,不要把搜索位置注意听这句话,不要把。不要把搜索位置移回已经比较过的位置,而是继续把它往后移,这样就提高了效率。
07:03
那首先我要解释第一句话,为什么说BCD已经比较过了,来,大家想一想。假定注意听这句话啊,假定我们让A和B进行比较。假定我们的A和B比较,其实A和B肯定是不匹配的。接接着你肯定会继续继续让这个后移嘛,就让A和C比较肯定的又不匹配,然后你还会让A和D去匹配,大家大家有没有发现,其实我让这个A。我这个只串的A跟他原创的BCD比较,这三个工作其实是有可能是无效的,或者说多余的,为什么呢?大家有没有发现你在进行这个A。跟B比较值钱,是不是这个BCD已经跟已经跟前,这就是说大家看这这条线啊,我画粗一点,就是你只串的BCD这几个三个字符,其实曾经在上面这个过程已经跟这前三个比较过了,而且是相等的。
08:05
是不是这点大家能认同吧,就说你A后面的三个字符。BCD其实已经跟在上一次已经跟BCD已经比较过了,是吧,这是肯定的,所以说,所以大家看。如果,如果我们,我们知道abcd。如果说我们知道A。他。他干什么呢?因为因为你这个A它不不等于B,也不等于C,也不等于D,这个大家是能够从字面上看出来的,就说A它确确实实不等于BCD,而刚才我们也确定了B,从B后面的三个字符,BCD已经跟他匹配过,它们是相等的,而你你你也知道A是。A4和这个BCD不等的,那么你想你让A去跟后面这个BCD比较,他肯定是不相等的,这几个工作肯定是没有意义的,对不对。
09:02
但我刚才说的这句话呢,有一个问题,什么问题呢?就是你怎么知道你这个A。跟后面的BCD是不相同的。这是一个关键。我怎么知道A,就说如果说我们知道A,我们我如果我知道这个A,就是我现在标的这个A和后面的BCD3个是不相同的,那么。大家知道,那就大家大家就应该知道A再去跟原先匹配过的BCD比较是没有意义的,但是我怎么知道A跟后面的BCD不相同呢?好,如果你问到这个问题,那我告诉大家,你就问的这个问题问的很好。是的,我怎么知道A和后面的BCD它是不相同的呢?或者说我怎么知道后面有三个是可以不比较的呢?这里就涉及到一个叫做部分搜索词,也就是我们涉及到一个自串的前缀和后缀,它的公共的部分内内内内节的知识点是,也就现在我们要解决一个新的问题,就是怎么知道。
10:05
能够找到一个部分搜索词。我就不写了啊,部分搜索,部分搜索词能够建立起来就解决问题,这里面涉及到怎么去找一个字符串的前缀和后缀的功最长的公共部分。那么如果这个问题就直接导致待会儿我们要讲的一个部分匹配值或者部分搜索词,那这个部分搜索是什么意思呢?好了。我们刚才已经把问题说的是说你在A进行这个BCD这个比较的手实际上是没有意义的,那我怎么知道它没有意义呢?因为我可以建一个搜索词。这个搜索词也叫部分。匹配表这个部分,匹配表这张表它是怎么产生的,我们后面再解释解释,你们先看一下。这个搜索词这个表怎么看,注意听啊,这个有有有点绕,我慢慢讲。
11:01
这句话怎么解释呢?就是说如果是字,字如果是A。如果是A这种字符串,那么它的部分匹配只有零。啊,如果是B,如果是AB。注意听啊,应该是看着AB,如果是AB这个串呢,它的部分匹配就是零。如果是ABC。ABC往后面再多了一个C,那么它的部分匹配也是指我就直接说最后一个啊,大家看,如果你的这个字符串就是你这个子串是abcd。好,如果是这个串,那么它的部分匹配值就是一。至于为什么推导出来是一的,我待会再讲,大家不要着急,因为这个算法不是我们想的那么简单的啊,OK,先理解到这里,那现在呢,我们接着往看。他下面又给了一个公式。已知空格D不匹配是前面六个字符A,前面六个字符是ABCDAB,它是可以匹配的,查表可知,最后注意查哪个呢?你要查ABCDAB,也就是查这个。
12:12
到这个串,它的部分匹配值就是。二。是这样看的啊,不能只看这个B,你看前面还有个B呢,对不对,你要看abcd这个串它的。部分匹配值是几呢?是二,好,有了这个二过后呢,它的这个公式是这样算的。也就是说你按照暴力匹配先移动到原先那个位置,然后实际上应该移动的位置是什么呢?已匹配的字符数减掉对应的部分匹配值一匹配的字符数字其实是六,再减去你这个部分匹配值就是二,也就是说应该是四,也就是说实际上你应该在你原先那个按照原先那个位置后移四位,而不是后移移位。注意听这句话。
13:00
也就是说,如果我们有这个搜索词的这个部分匹配值的话,我们实际是应该在原先这个位置后移四位,而不是后移移位。那么同学们可能有点不理解了,那什么意思呢?大家看,如果我给大家按照这个来玩。我们先前是在这个地方产生不匹配的,还记得吧?好,我给大家。呃,画一下大家应该就很好理解了,注意听哦。关于这块呢,很多书上讲的比较绕,我就直接说这个规则,大家看它的规则。注意这个规则是怎么来的,就是这个匹配部分,匹配表怎么算的,我待会再讲,第二个这个规则怎么来的,就是人家这这个KP这几个哥们,他们总结和发表出来的一个算法,你就先暂时不要去。去说,诶为什么是这个公式。对吧,那你要这么去讲的话,这个算法就是就相当于说你你你就说他肯定是通过一个方案来来计算出来的,我们也可以解释清楚为什么为什么是这个,所以说我们先呢把这个算法搞定,再去理解为什么走代码的时候再去说为什么好,它的算法是已匹配的字符数减去,也就是移动四位应该怎么移呢?也就是说应该是这样移,注意听啊。
14:19
也就是说,按照他的这个思想呢,应该是这样的移动。一栋一位,移动两位。移动三位,移动四位到这儿你看。到这好,也就是说按照我们这个部分匹配表来玩的话呢,是移动四位,而不是像我们刚才所想象的那样,哦,你原先到这匹配往后面移动一位,让这个A和B比,不是的,它是移动四位。为什么移动四位,就是因为他知道BCD是部分已经匹配过的它,所以说已经有两个所直接往后面移动。OK,那移动的话呢,注意听啊注意听不着急,咱们一一点说,接着往下看,还看我们这个这个东西,那么接着他说因为空格与C不匹配,搜索时还要继续后移,这时已匹配的支付处是二,就它这个还要进行一个匹配二,那么这个地方它就涉及到我们到时在匹配的时候有个外循环去找。
15:19
什么时候才会?才才会去停止下来啊,现在你还有两个匹配到的,那么这个两个匹配的是ABAB呢,大家看这个AB,它对应的部分搜索值应该看这个零,也就是说相当于是二减零,也就说应该我们在这个搜索继续往后面移动两位。那移动两位变成什么呢?再移动一位,移动两位,多出来了。好,到这来了,到这来了,过后我们这再往下面看。再往下面移动,因为空格与A不匹配,继续后移好,这时注意同学到第十步的时候,就是按照我们以前那个方法又来一个个的比啊这个因为这个前面已经不能再去用部分匹配表了,那这个时候再去哦,这匹配成功又匹配又匹配又匹配又匹配又匹配好,到底又不匹配了,又按照刚才那个方案,又刚才那个方案敲跑跑跑跑跑跑到这。
16:12
跑到这个地方的时候再匹配ABCDD,好匹配成功。好,那么也就是说,也就是说他这个他这个匹配的时候呢,他要充分的利用我们这个部分匹配表,最后在这匹配成功了。我不知道大家听懂了没有,其实大家如果没有听懂的话呢,只有一个原因,只有一个原因就是说它为什么是这个部部分搜索词是怎么产生的,为什么有这个部分。部分的匹配值,或者叫搜索值,这是第一个大家疑惑的,第二个呢,大家疑惑的是什么呀?就是说这它为它这个它这个移动的原因是为什么,对吧?这是第二个疑惑的,但是我想不管你们怎么疑惑,但有一点是可以肯定的,就是你至少知道。这个KMP算法的他的一个思想是不能够按照暴力匹配那样,每一次哦,就傻乎乎的在这,我我发现一个匹匹配不了,我就往这移动移位,再去让这个A。
17:11
A和BB,然后发现又不匹配,又在移动,移位又在移动,肯定不是这样的了,也就你至少要知道。他有一个方法,或者有一个算法,能够快速的把这个没有必要再去匹配的跳过。你只要理解到这一步啊,你你至少要理解到这一步才行,那么理解到这一步过后呢,我们下面呢,同学们,下面我们接着来看这个部分匹配值是怎么产生的,好来玩一把,那么部分匹配表或者叫部分匹配值它是怎么产生的呢?首先要给大家介绍一下谁什么叫前缀,什么叫后缀,来聊一聊,所以前缀我们用这个bread面包这个单词来看,前缀它一共有几个呢?有四个。也就是说它可以是BB r b reb rea,不能再加D了,再加D是全部了。
18:03
后缀是什么呢?后缀是。四个最长的是这个三个两个一个好,这就是所谓的前缀和后缀的概念,明白了,明白这个过后呢,我们现在就以我们实际例子ABCDABD为例,假如我们字符串是A。假如我们这么说,诶,它的前缀和后缀都为空,就是他没有前缀也没有后缀。因为它就一个字母嘛,所以说这个时候呢,它的元素程度共有元素程度为零。啊,共有长度部分匹配值就是前缀和后缀最长的共有元素的长度,这个是他们总结出来的一个规律,就是部分P就是假设我我有一个前缀,我有个后缀,我们把这个前缀和后缀这个集合看最长的那一个共有元素的程度,就是我们这个串串的。部分匹配值好,你看A,它没有前缀,也没有后缀,那么就是空集合,空集合那么这个元素长度就为零,也就是说部分匹配值就为零,那么AB呢?我们看AB,它的前缀为A,后缀为B,共有有共有元素吗?一个都没有,这是A值,B没有说它也是零,这就是为什么你们刚才看到的这个匹配角是这样写的,AB这是零,这是零的原因。
19:20
好,紧接着我们看ABCAABC它有的前缀是AB或者是AB,后缀是BC和B,大家看你们注意观察,这个时候它有没有共同的这个元素,一个都没有,所以说长度人合力abcd也是一样啊,Abcd它的前缀是这三个后缀实际上有共有的吗?有共有的这个券吗?没有,所以长度也是到了abcd,好,这个要注意了,ABCDA它的前缀有这么多,它的后缀有这么多,大家看里面有一个是。共同的哪一个?同学们看到没有,我换一个颜色。大家看有没有发现这里面有一个共有的部分是。
20:00
A。这有个A,这也有个A,它们共有的只有一个,就是A,这时共有元素A,它的长度为一,所以说所以说我们这个匹配表应该是这样的adcd。A,好,那这个前面是0000,到到这个ABCDA的时候,这个就变成一了。明白,接着看B,又来个bab的ABCDAB的前缀是这么多,后缀是这么多,它共有的元素是哪一个呢?大家看它共有的元素是AB,看到没有?AB这边也有一个ad,那么长度是二,所以说如果再加一个B的话,那么这个串的它的部分匹配值就应该是二了。明白,我们再加一个D,好,再加一个D过后呢,你会你会发现诶。共有长度反而没没有了,你看这个时候你看它它有共,它有共有长度吗?呃,共有的这个元素有吗?你会发现根本就没有了。
21:04
就没有了,没有的话。它的长度就为零。是吧,你看是不是没有共有长度了,但是零,好,这个又变成零了,同学们大概知道这一个部分匹配值是什么推导出来的,以及怎么看了吧。应该大大体能够清楚是什么意思了吧,也就是说你千万不要认为是哦,A对一个零,B等于零,这是错了,应该这样看,A串对它的部部分匹配值是你看到这个B的时候呢,你你应该想象出来是AB串。它对应的部分平面是零,当你看到D的时候,你应该反应出来是abcd这个串,它的部分匹配值是零。这样看才对。好。同学们那。那这个部分匹配值根据刚才这个生成,我们就是这样一个表就拿到了,那到此KB算法的思想就分析完毕了。也就是说你在进行这个KP的时候,你的步骤应该是怎么玩呢?你的步骤第一步你要先得到,先得到这个纸串的什么呀,部分部分匹配表,是不是第二步你才能使用我们这个部分匹配表完成KP的一个匹配,而匹配的时候呢,要充分的利用我们的这一个。
22:28
这一个思想,哪个思想就是这种思想。哎,哪个是想大家看是不是在这里有有一个说法呀。是不是这种思想?就这种事情就是呃,怎么怎么去移动,而不能说我就每次就移动一次,这时你这个值其实就是藏在我们的这一个部分匹配表里面的,待会儿呢,大家从代码里面能够看到这个思想的体现。好,各位同学,那关于我们KP算法的思路分析,就先给各位同学聊到这,那有些同学说老师这个我还是没有听明白,没有听明白没有不要紧,有两个方法,第二一个你自己多看两遍,第二个实在不行,你觉得老师这块讲的还是不够特别的透彻,你们也可以来看一下这篇文章,但我告诉大家,这篇文章讲的是很细的啊。
23:21
讲的很细,如果说你没有一点数学功底,可能还不一定看得懂。明白吧,就是有时候他讲的特别细的情况下呢,你反而不一定听懂了。OK。但是呢,我我建议大家如果说确实想彻底想搞懂,也可以参考这篇文章,好,现在呢,大体的核心思想,最主要的核心思想,我们已经就讲完了。
我来说两句