00:00
同学们,我们把刚才讲的KKP算法用代码给大家实现一下,来走一个。那我新建一个类。KP。Not all good reason。就是咱们算法啊,TP算法。现在呢,我们还是老规矩,首先把这两个串串给他整起来。一个是实训,一。这个十寸一呢,就用刚才我们讲课时候用到的这个串,没问题吧,同学们。把它放到这里来。这是第一个串,第二个就是我们的纸串子串,大家还记不记得我们用的是这个串abcd。Abd,那也也就是说将来你这个指串不一样,产生的部分匹配表它也是不一样的,或者部分匹配值是不一样的,明白,那现在呢,我们是不是按照这个步骤来讲,我们第一步应该先写一个方法干什么呀?先写一个方法获取到获取到一个字符串,但这个串呢,一般我们是指的子串。
01:15
指串它的什么呀,部分匹配值。对吧,部分匹配是A。叫的部分匹配值。匹配。OK,没问题,就是拿到一个串的部分匹配值,嗯,那么这个部分匹配值咱们怎么拿到呢?根据刚才的一个思路,我们先来完成一下public void。Int,最后我返回的是一个int数组,因为同学们刚才也看到了我在这地方拿到部分匹配值的时候。拿到这个部分匹配时候,它整个最后我们用这个数组的下标来表示它是第几位就可以了,明白我的意思吧,就说比如说A,按照我们这个abcd来说呢,它这个第一个A代表是下边为零,所以到时间这个就零,下边为一的也是零,下边为二的是零,下边为三的是零,下标为四的就这个呃,就是ABCDA了这个串,那么是一下标为五的为二,下边为六的也是零,就这样子的,这就是我们产生的部分匹配,匹配值啊,匹配值也是表的意思啊。
02:21
部分匹配值的一个表吧,这样就可以了。比部分匹配指标,那现在呢,我们写个方法就叫k p next。那你怎么样才能得到这个部分匹配表呢?非常简单,你给我一个串。对吧,假如这个串我们叫这种目标,就是我要匹配的一个串,那你拿到这个串以后,拿到这个串以后你应该怎么做呢?首先。因为你要返回一个这样的数组嘛,所以说你先要创建一个跟det。这个字符串。长度相同的一个int数组是这样子吧,首先创建一个。
03:05
啊,数组就是next数组吧,数组保存。保存。部分匹配值是这个意思吧,同学们,保存我们部分比值,那我起个名字了,跟上思路,同学们,Next等于什么呢?哎,这个就等于new一个int。然后大小我们看一下大小呢,就等于Dst.N就可以了。认识OK,好,第一个方法就完了,第二个大家还记不记得,如果只有一个。如果我们只有一个数据的话,不管是你,你这个串是什么串,如果只有一个字符串,如果你只有一个字符串,那它一定是一个零,我不知道我说清楚没有。我把这个写清楚啊,如果如果自DTDT的。这个长度就是说,如果字符串是长度。
04:05
二长度为。为什么呢?为一为一的话,它对应的下边不就零吗?对吧,那么它的这个部分。对,部分匹配,匹配值就是零,所以说我就去写个零。因为我待会遍历的时候,我就不用从零开始了,好我开始写了啊,然后这边就写个I,然后这边呢。我们来写一个。这样写,写个I,再写个解等于零,不着急啊,我们一会解释。然后这边我要我要去对所有的这我要对DST整个串进行扫描,所以说这个I呢,我要小于Dst.ne就可以了。就不要超过这个范围,然后我们的I加加。OK,来写一段代码,我们先由简单到复杂,好吧,先要简单,我们先考虑,就它有一个规律,它有这么一个规律什么呢?注意听,如果注意听这句话啊,DT。
05:07
如果DST它的char at。如果这个I啊,它等于DST。点叉爱。解。二节,那这个I呢,我们刚才讲了,从一开始,我这就从一开始了,I等于节在这种情况下呢,在这种情况下,这个就发现有一个就说这个条件满足,如果这个条件满足的话,就应该是什么,当这个条件,当这个条件满足时。注意听,满足时注意听啊,那么就会出现一个什么情况呢?就是这个我们叫做部分,叫做部。部分匹配匹配。匹配值就就需就是要加一。
06:00
就加一,那加完一过后呢,我就直接把它放在这个next数组里面就可以了,那这个时候应该对应的是什么呢?I等于J。因为你现在是在对第二个,就是因为你你现在字符串已经到第二位了嘛,对吧,所以说这个I呢,就对应你这个字符串的这个位置,就等于几,这好现在我们就可以返回了。Next说,老师这样就写完了吗?当然没有写完,但是你现在可以撤了已经啊,我现在是由简单到复杂,你们来看一下,同学们,给你们给你们玩一把哈,看看你们能不能理解。给你们玩一把next等于什么呢?K p next,我传一个最简单的来,我们验一下。假如我写个AA,我问同学们一个问题,如果是AA的话,我们进到这里面来,这个部分部分匹配。这个next应该是什么样的?第一个上来是不为零呢?第二个看一下AA这个词串,它的前缀是不是A,后缀也是A,记得吗?刚才我们是讲过这个东西啊。
07:03
是不是还记得是怎么推前前缀和后缀的吧?假设我们,我们是这样一个串串。A,它的前缀是不是有一个A,后缀也有一个A,那这个时候是不是就等于一了。对吧,也就是他等于一,这就是为什么我这写这个条件,如果我们这错了一位,初始化是错了一位,如果你这个I等于J。I等于几,就是你你的前一位和后位,在这种情况下啊,前一位和后位相等,那么我们就认为有一个匹配值,有一个匹配值就就加一,原先是零嘛,就加一个一再把它付给它,也就是说这个时候它应该返回零一,大家看能不能理解,好,我先把它输出。我把它输出来,那这个输出的时候呢,就next等于加上谁呀二。Always。点two three,我给大家看一下是不是跟我们想的一样,玩一把来走运行。
08:02
好的,我们运行看你果然是零一,那有些同说你再加一个呢,你再加一个,你看是几啊,那就是那你那你想嘛,如果是三个A的话,大家想它是什么样,是不是前缀有AA,后缀也有AA啊,那最大就是二了,诶那这个变成二了,因为你你在进行判断的时候,你发现你这加加加完了过后,我这个节也我的I也加加了,是不是判断这个这个第二个和第三个是不是相等的,那这个时候呢,你会发现它的确是012。零二正确的,但是这种情况呢。诶,他有没有考虑假设我是个B,你麻烦了,你看啊加一个B。好加个B,后面这个B它也这么这么玩了,这就不对了,因为这个地方产生一个多的数,数多的一个其他的值的时候呢,你并没有进行一个重新的考虑,那这个时候应该是怎么样的一个逻辑呢?注意听这句话啊,注意听当我写一句话。你现在只考虑了DST叉的I等于DSD叉的节,你没有考虑这两种不懂的情况,就是当这两个哥们不等的时候呢,这个时候情况就不一样了,当他不等时,我们需要干什么呢?注意听这句话啊,当这两个不需不等的时候,不等的时候我们。
09:16
我们需要需要从。写到这里啊,我们需要从哪里呢?从这个next节减一,就是从它前面的从部分匹配值的前一个位置获取新的这个解。新的理解,我先把这个代码写一下,你们看一下对不对,当然还要满足,同时还要满足。同时要慢。如果如直到什么呢?新新的结就是。直到什么时候退出呢,直到。直到,直到。直到我们发现有有什么呢?有这个条件满足时,我们才退出。
10:03
这个条件,直到有这个条件成立时。成立时代推出。整理才退出,也就是说他一直在这个next表一直往前面去找。一直往前面去找,OK,那这个时候呢,这个代码就应该变成这样子了啊for循环it。ID什么呢?我们想一想啊,那就是应该是,那就不应该是for循环了,应该是Y循环,那就写个Y循环。如果这个结大于零,因为你在进行这个处理的时候,这个节要保证大于零,对要保证大于,在这种情况下,我们要满足只要这个条件。成立,那说明我们这个就一直往前面找。就说我们一直要从这取取,直到这个条件相等才退出,那这个时候这个条件应该怎么写,就截等于next。干什么呢?解减一这个代码就。洗完了。
11:01
啊,这样写就行了,就这么一句话就搞定啊,就这么一句话就搞定,也就是他这个是相当于说,如果我发现有一个不相等的情况下,我就从这个部分匹配表的这个节减一的位置去更新这个解,这个是它的一个算法的一个跟基础,啊,这个是他一个算法的基础,这是。这是。这是什么呢?就是KP算法的算法的一个基础算法的一个特点啊,它的一个一个核心这样写啊,核心核心点。核心点,那么你可以去用这个KP去进行验证,它总是满足这样一个条件的,它总是满足这样一个条件的,OK,那现在我们再来看一下。这个会出现什么情况呢?这个地方就应该不再是二了啊,那这个肯定就不再是二了,那就是112,后面这个肯定不再是不再是三了,四我们运行一下。好,我们运行,我们运行看的是0120,这个是正确的,那这个到底正不确,我们没有玩过呀,所以说我把这个换成我们已经测试过的,把它换成这个abcdd OK运行我们发现呢,跟我们想的应该是一样的,000012。
12:16
零代码写完,也就说这个特点,如果你们想不想不起不确定的话,你可以拿这个去验证,拿这个验证你会发现他就是这样一个特点,这是KP算法的一个核心点。啊,核心点也并不是很难,对不对,就说等的时候咱们结加加补给他如果不等的时候同时还满足结大,结大于时候,我们就一直要找的一个相等。在没有找到这个相等的时候,就把这个就把这个J减一付给这个结,就是相当于回回回溯啊回溯。好,那么当我们把这个解决过后呢,下一个方法就摆在我们面前了,下一个方法是应该是什么呢?就是咱们写搜索算法了。有了这个TP,那下一步就是写出写出。写出我们的KP搜索,对搜索算法也不难,来,同学们写一把。
13:08
嗯。写吧,这样子啊,我们把这个方法可以。可以封装起来,如果不封装也可以,那就写到这吧,好吧,那就写到这吧,Public static。Int对不对?Int,然后k PK MMP search搜索,那你搜索的时候你要给我传什么呢?肯定你要把STRING1给我传过来,这是跑不了的,STRING2你要给我传过来,这个也是跑不了的,然后呢,还有一个就是我们的部分匹配值的这个表要给我传过来。没问题吧,那么同样我在这做一个注释,十寸一就是我们的。那个大串就是原原创。原字符串圆就是圆。
14:01
往下走一下原字符串,对这个STRING2呢,就是我们的。指串。就是需要去在这个原串里面去找,有没有这个指串的啊,这个是指串。子串。OK,串,那么next呢,就是我们的部分匹配表,这个部分表是哪一个呢?是指串,指串是这个指串对应的不。部分匹配表别别搞错了,因为部分这个。部分部分匹配表,它是跟这个串相关的,对吧,所以说你你不能乱写一个过去一定要把这个尺寸二的指串的部分表传到这边来,那返回值是什么呢?呃,如果是负一,就是没有没有匹配的,没有匹配到。否则返回第一个匹配的位置。匹配的位置。
15:00
明白好代码我们就写到这,那现在开始写代码了,整体这个思路呢,也非常的简单,我们就遍历。哦,我们干什么呢?便利我们哪一个村啊,你找的时候是不是是以这个最一来。走的呀,是不是就是实训一,如果是整个变完了过后没有找到,那就那就没有了,所以说你在这个过程中应该是以实训一来进行这个这个便利的好for循环,我写一个I等于零,节也等于零,这个节呢,你可以理解成是这个节是指向我们是string。二的,也就是说有一个I呢是指向寸一,而寸J呢是指寸指向这个寸二的这种感觉好,那I只要只要是小于string一点,认识我们就可以string一点。那代码哪写错了啊,看看I小于准一点。认识。
16:01
演技。TH是吧?好,然后呢,这边我们来一个什么呀,I加加。爱家佳。好,哎,加加这个I,我刚才是哪里写错了呢。这地方不能写成。分号要写成逗号对吧,别写错了,写错了它不提示遍历的时候,我们就开始来做一个最简单的,大家一下就明白了啊,你看我写个最简单的,怎么写呢?如果我你看这个这个代码,大家看能不能看懂,我相信大部分同学都能看懂啊,Chart at I如果等于string2.char的艾特杰各位。各位,然后我要做些什么事情呢?我叫re。我就我就结加加对吧,我就结加加。当这个处理完了过后,我做一个判断,如果什么呢?如果这个解它等于了什么呢?我们使劲二点。
17:00
那这个时候就说明我找到了,是不是同学们这个就找到了,那找到了我就返回下标,这个下标应该怎么返回呢?同学们想是不是应该是I减J加一了。I减一下,因为我们这边是进行这个I节都是从零开始的,所以这个返回是I减节加一,然后这边呢,我们就返回一个负一,如果找不到就返回负一,我们现在可以试一下。我们现在可以试一下,看看能否成功啊,能否成功,当然我还没写完,肯定还有一些漏洞哈,因为连这个next的我就没传进去,所以说不着急,我们先看一个最简单的,比方说现在呢,我把这个改成这么一个圈,你们看看是不是已经拿到结果了。来,各位朋友,假如我把这个STRING2改成DBC。BBC,那我们来先看一下这种代码,它会怎么样走,我用int in int index来接收k MP search,然后呢,把11,十二传进去,Nextx也传进去了。
18:07
那么我输出这个index。Index等于加上index。对,你来哦,同学们看一下。我们先看现在我传的这个串儿,那当然。传销串是BBC这一大串,然后我要匹配的是BBC,其实这个是最简单的了,那近代过我们先看这代码它会怎么走,I等于零,截等于零,好,I结是不是相等的J加加。J加加J等于这个十寸二的长度吗?还没到是吧?没到没有到的话,同学们是不是此时此刻J加加相当于说I加加了减A加加,再去判断是不是相等的,是不是又相等。又相等是不是结又加加L又加加好,最后它每判断一次,就判断这个结是不是等于十分二的长度,那因为我们这个是最简单的,它不停的走,第一个匹配上了。
19:01
加了个一,第二个匹配上了,加了一个一,第三个又匹配上加了一个一,好到这个时候它就结就等于这个它的长度了,也就是说当这个时候呢,结就已经等于了三。那么这个时候I等于多少呢?同学们,I等于多少了?你们想解是等于三了,I等于多少?I等于,I等于多少?大家可以想一想。爱你多少?对,你想你在这个节的,这个节是不停的加加,你I也在不停的加加,是不是,所以说我们可以来在这打一个断点,你们来看一下,一目而了然,来走一个我们运行一把。当这个条件满足的时候,我们来debug一下,走运行一下。哎,运行一下你们看。根据这个第八个结果,大家一目而了然,往下走,大家看这个时候第一次。结是等于一的,显然它不可能进来,接着往下走,进去再来走,是不是又相等,结又加加,结又加加,过后呢,这个结它等于二了,还是没有匹配完毕,接着再往下走,又匹配上,结又加加,结又加加,现在结呢等于三,I等于多少呢?我们看一下I现在是等于二了。
20:14
是不是因为你结加加了,你结加加了I还没有机会加呀。是不是你你结加加了过后,I还没有来得及加加,所以说I还保保持圆心这个二,那这个时候它就进去了,进去过后相当于是I减去一个,解就是二减三,二减三等于多少呢?等于负一,负一再加一个一,好这个时候就返回了一个零。代码写完,也就是说这个时候index呢就已经拿到了。我往下再走一步,会输出一个零,好,这个最简单的案例其实大家已经看到了,也就是说如果我们不考虑用部分匹配表,那么这段代码在这种情况下就是可以用的,但实际上呢,它有漏洞,大家看,当我把这个打开。
21:03
我写成ABCDD的时候,因为你不不是从头开始匹配,而且中间呢,有一个匹配的过程中,还在匹配的过程中,又匹配的一部分又没有匹配到的情况,在这种情况下,我们再输出这个index,你会发现呢,它就是错的了,因为我们来给大家演示一下,来运行一把。那运行过后你会发现这个结果才八,显然这个不可能等于八。你看啊,Abcd它匹配的时候,它应该是匹配到这个ABC,这应该是哪个位置了,数一数。零一二三四五六七八九十七十二十三十四十五,也就按理说应该输出15,但是呢,你输出的是八,原因就是因为你在匹配的这个过程中有一部分。你你只考虑他不停的。佳佳,你没有考虑这个节的位置重新定向?
22:01
对不对,没有考虑,所以说最后结果肯定是错的,那我们怎么样能够来去调整它呢?好,注意看我这段代码。这段代码呢?他的思想是样子。需要从。应该是这样一个条件啊,同学们,他仍然是没有考虑这两者不同的情况。你这只考虑相等,相等加加是正确的,那么我们现在还需要考虑。写上需要考虑或者要处理,当这两个不相等的时候,应该怎么去玩,那我把这个说清楚,这也是这个也是KMP的一个核心,核心点。天算法的核心点,追听。核心点和前面很像,和我们获取这个next,呃,K p next很像很像,我把这个代码给他写一遍,你们就一下就明白了。还是老规矩Y循环,首先呢结要这个时候就是说当应该是处理这个不相等情况,要调整什么呢?要去去调整。
23:08
调整这个节的大小。那首先我们要满把保证结大于零,因为结不大于零,到时间我们就会越见当,而且满足这两个不相等的情况下,我们要去调整。诶怎么调整呢?非常的简单,一句话就可以搞定,还是跟前面这个逻辑一样的,你原先是怎么去获取这一个部分匹配值的,你就按照这个方式来去修改,我们这个节,就相当于说用我们这个部分匹配表就可以了,好,这地方为什么错了?改成这个。改成这个英文的好大么就行了,就是这样子做就OK了,也就是说这个地方我们就是KP算法的核心点,它能够在它不相等的时候让这个节重新调整,调整的原则是让这个节往它这个就是往我们这个部分匹配表的前面去找,直到找到一个相等的位置才停下来。
24:04
这个也是它的核心点,那么同学们可以去验证一下,可以验证。你按这个规则去验证就就是正确的,那现在呢,我们再来看,现在再去执行这个呢,它就应该等于15了。是不是等于15呢,我们运习一把。诶,我们可以看到的确是15。的确是十好同学们,那关于我们这个KP这个搜索算法,还有它的一个部分匹配值的一个创建呢,我们就讲到这,其实这里面最麻烦的就是这句话的理解对不对,就这句话理解这句话呢,就是KP算法的一个核心点,就是也就是说当他不等的时候,我们要从这个部分匹配表让这个节减一去更新我们这个节,这是它的一个核心点。大家可以去,这是怎么总结出来的呢?说老师你怎么知道这个这个这么写呢?这是KP算法它的一个公式,或者是你可以当成是它的一个规律来记,都是可以的,明白意思吧,好了,其实就这么一点东西,把它记记清楚就行了,如果同学们要彻底的了解凭什么这么做,OK,那韩老师只能让你们去看这。
25:13
看这篇文章了。因为这篇文章它是讲的从底层来把他的一个数理逻辑讲清楚,讲明白,但是呢,如果你只是站在从KP原理的理解,以及我们能把代码写清楚,其实这一段就够了。因为大部分情况下呢,别人只是让你去写一个KP,并且阐述一下KP的一个他的一个核心,怎么去求出我们这个。天就说怎么去求到这一个部分匹配表,以及KP,它的一个检索的一个流程,也就是我这画的。前面的一个算法和KP这个部分匹配值,它是怎么去记得到的,这个这个原理它让你阐述一下,把代码写一下基本就OK了,包括有些同学去考研,他也是站在这个层面的明白。
26:03
因为算法嘛,我们更多的是站在应用的角度,就是去用它,对不对,好各位同学,那关于这个KP算法呢,就给同学们聊到这里,大家把它好好的理解一下。
我来说两句