00:00
同学们,我们来看一下KMP算法。我们来看一看一个关于KMP算法的应用场景,叫字符串匹配问题,这个问题呢非常的简单,他是这样说的,他说有一个串是这个样子的串,然后呢,另外一个子串是这个串,它要求我们判断10STRING1是否含有十寸二,如果存在呢,就返回第一次出现的位置,如果没有返回负一,就这么简单。各位同学,拿到这个题你会怎么想啊?一般来讲,大部分的人呢,就会采用逐一匹配的方式,这种方式呢比较简单,也比较好实现,但是效率比较低,俗称暴力匹配法,那么我们来看看暴力匹配它的这个算法是一个怎样的规则,大家看,如果我们使用暴力匹配,它的思路大概是这样子的。我们假定十寸一匹配到了I。String指串STRING2匹配到了节这个位置,也就是说有一个索引I指向STRING1,有一个索引节指向STRING2,那么这个这个时候呢,有这么一个情况,假如当前STRING1的II指向STRING1的啊,STRING1它等于STRING2节这个时候呢?
01:14
假设他们相等,那么这两个索引同时往后移,继续匹配下一个。如果说他们在下一次匹配不成功,也就是说失配了。失败了,失败了,这个时候呢,我们让这个I变成什么呢?让这个I等于I减去减减一,这个是个括号。那也就是说相当于回到原先那个I后面那个位置移动移位结呢,重新治理。对,那也就相当于每次匹配失败呢,I都会被回溯截至零,这样的匹配方式呢。它会存在一个大量的回溯。每次因为只移动一次,若是不匹配,移动到下一位接着判断,浪费了大量的时间。这个呢,效率是比较低的。啊,那有些同学可能还没明白这一个暴力匹配算法到底是在说什么,我简单再给大家说一下他的问题之所在。
02:06
那还回到前面这一个幻灯片,我们来想一想,它是什么问题啊,比如说现在这这个是上硅谷的上,他不停的匹配,不停的匹配,匹配到这了,假如说这个地方匹配到。我们STRING1的这个地方,我们叫I挨到这来了。那么节呢,显然是指向这个位置的,这是节,这这边是结好,现在上和上相等。好,这个后移。这个结也后移。呃,归也是相等的,继续后移到谷,这个也到骨也是相同的,这边到你也是相同的,这边也是到你,这边呢,到上归骨的上,这边也到上硅谷的上,这边到硅硅谷的硅,这边到了硅谷的归,好,问题出现在下一位。我换一个颜色,换一个比比的颜色到这了,到这的时候呢,我们发现STRING1的指标I它指向了空格,而STRING2它的这个索引节指向了你。
03:08
大家可以看到这个时候不匹配,因为一个是空格,一个是你,那么如果是暴力匹配,他会怎么做呢?他首他会这样子,他先让这个I,它会让I等于什么呢?等于I减去解减一。也就是说相当于说ii等于I简洁加一,那这个会到哪里去呢?其实相当于把这个I指向到了。硅谷的硅。对,上归谷,上归谷的这个归到这来了,到这来的话呢,这个结会至零,那至零的话,这个节到哪里去了呢?各位同学,结相当于指向了这个三个骨的上,好问题就出现了。那也就是说,一旦有一你,你辛辛苦苦匹配了这么多。那么这个时候他直接就回到I的下一位再去比较,其实这里面是有重复重复的过程的。
04:04
这个回溯它的次数很多,效率比较低。OK,这个就是我们所说的暴力。匹配的一个算法,那暴力匹配算法虽然比较笨,比较傻,但是呢它也算是一种解决方案,因此呢,我们也把这个暴力匹配算法给他写一遍,大家体验一下,那么写暴力匹配算法呢,主要是后跟后面我们写的KMP算法进行比较。然后呢,你比较过你你会发现KP算法它的效率是比较高的,而且想法它的是一种很优秀的设计设计算法。好吧,那我们把暴力算法给他写,快速的写一遍就可以了,来吧。我们写一下。写个包。点。叫KP没问题吧。我们写一个类。我们快速写哈,这个比较简单,快速的写violence。Violence。Match暴力匹配。
05:01
这是写的一个类,那么这个地方我就直接上一个方法,就是暴力。暴利匹配算法实现好吧?那public static返回一个。然后暴力匹配它的方法呢,我们把这个大写的V改一下就可以,这时需要你传两个串进来,比如说第一个是我全屏一下。十卷一,第二个是十卷二,就按照刚才那个名字写就可以,那第一步我们先干什么呢?把这两个串转成一个字符数组好吧。比如S。比如叫S1吧,这个也无所谓,就叫S1。嗯,是S1,我们应该等于什么呢?就使均1.twochar位,我们再写一个字符数组,叫S2,没问题吧,同学们使STRING2点也转成一个字符数组。好的,那现在呢,我们再分别得到它们的长度,比如说S1的一个N。
06:03
等于什么呢?S一点。这个是STRING1这一个字符数组的长度,后面我有用,再来一个string s2 S2这个N呢,我们也拿到S2.n没问题。拿到以后,我们刚才分析出来,在整个过程我们需要一个I指向10STRING1,我们需要一个节指向十寸二。那这个时候就相当于指向我们S1和S2这两个字符数组,是不是这样,那我现在把这个I初始化为零,解初始化也为零,我先说做一个说明I。相当于这个索引I,这个索引它指向S1。对接这个索引,索引它指向S2,没问题吧,同学们好,现在呢,我们就用一个Y循环就可以了,如果I小于我们S1,点S1嫩。
07:04
就说明他还没有越界。因为I是指向。这个S1的嘛,所以说只要它小于这个范围,就说明还可以继续去进行这个检索,那么解它也要满足小于什么呢?小于我们的S2能没问题吧,同学们。好,这这个地方的目的是要保证,保证什么呢?在检索时保证检索或者要匹配吧,匹配时不越界。不越界,OK?OK,把这个稍微格式化一下,那这个时候我们下面就有代码了,刚才讲过,如果说他们匹配上了,也就是说如果S1它的I等于了S2的这个解说明什么?说明我们匹配成功,是不是匹配成功,各位同学。匹配成功,OK。
08:00
那这个时候呢,我们就I加加,同时让解也加加后移嘛,同时后移else else说明它没有匹配成功。是不是没有匹配。匹配成功,那没有匹配成功,刚才我们已然把这个算法说好了,就是在在这种情况下,我们要处理的方案呢,就变成了这个列,那非常简单。非常简单。我们先让这个I等于。I。I减掉一个节,节减一。节减一没有问题吧,同学们再把这个节制为零就可以了,那么就写完了,那当我们这个Y循环结束以后呢,我们怎么知道它匹配了还是没有匹配呢?好,可以根据这个节的值来判断。就是我们现在要判断。判断是否匹配成功非常的简单。如果解它等于了我们这个。
09:07
什么呢?就是使君二论。因为他如果真的匹配成功,它不停的增长,最终会等于S12任对不对,在这种情况下,我们就代表匹配成功,我就返回对应的这个下标,各位同学这个下标应该是怎么算的呢?这个下标应该是什么?应该是I剪洁对不对,因为它它匹配到时候这个I也停下来了,截停下来了,那他们I剪洁的这个对应的值就是我们的下标,否则我们返回一个什么呢?负一就可以了。好,同学们,代码呢就写完,我们来测一下。测试暴力。A、暴力匹配算法。嗯,那这样子我们写个使卷一,使卷一就等于各位。就等于我们在这举例的举例的时候这个小串吧,十寸一就是个串串。
10:02
没问题啊,同学们,那么我们再写一个实训二。使君二,它等于什么呢?也等于我们刚才给大家看的这个串没问题吧,同学们非常的简单。现在呢,我们调用这个方法拿到一个index,怎么调呢?Violence match,把这个放进去。好,各位朋友,我们输出这个index就可以了,应该是等于多少呢?我们来看一下。各位,我们先不要运行,我们看他的结果,根据我们的分析应该是哪一个。各位同学看啊,往这找找找找找,找到这上硅谷匹配,但是呢,这匹配不上的,这是你硅谷你后面没有。好,大概应该是这儿位置,我换一个颜色,红色的应该是从这儿开始的,上硅谷拟上。上归你正确的,也就是说匹配的位置应该是这个上。
11:00
这个上,那么我们数一数应该是几啊,下边应该是几?第一个是零一二三四五六七八九十,11 12 13 14 15,也就是说如果正确是15来运行一把,我们看结果对不对,我们发现是15正确的,那我们找一个匹配不不到的,我加一个波浪号,肯定一个都没有,会返回负一。各位返回复议正确,好的同学们,那关于暴力匹配算法就这么样子,挺简单的,但是暴力匹配大家也看到了,性能肯定是不好的,因为他只要有一次匹配不成功,它整个全部回溯。这个代价是很高的,对不对,尤其是我们在做大量字符串匹配的时候,你用这个算法来玩的话,性能很低。因此呢,我们就提出在这个暴力匹配的基础上呢,提出另外一种算法叫什么呢?各位同学,就是我们的KMP算法,那关于KMP算法是什么,他的思想是什么,待会我们再为大家介绍。
我来说两句