用通俗易懂的语言搞懂字符串匹配算法KMP(图片很多)
前戏
在大家平时编码的过程中,肯定会遇到比较字符串,这种场景经常会在我们的日常开发中经常碰到。为了更好的通俗易懂说明字符串匹配过程,我们先来看个例子吧,有一个字符串“BBC ABCDABABCDABCDABDE”,我们如何知道里面是否包含另外一个字符串“ABCDABD”呢?大家思考10秒钟,能否自己想到好的方式?
其实有很多算法可以解决这个查找的工作,Knuth-Morris-Pratt算法简称KMP是最常用的算法之一。之所以叫这个名字,是因为三个人发明了这个算法,就以他们名字的首字母表示这个算法。网上有很多文章讲解这个算法,但是都是不太容易去理解,那本文呢,就是用简单的语言描述,让大家能够快速理解KMP算法,多谢大家支持!
算法图解
我们来解释一个名字,
搜索词:我们需要判断的字符串“ABCDABD”
- 首先,第一步很简单就是比较第一个字符嘛,字符串“BBC ABCDABABCDABCDABDE”第一个字符“B”和搜索词第一个字符“A”比较,显而易见不匹配,所以接下去的操作是将搜索词整体后移一位。看下图:
- 然后呢?再比较第一个字符,发现还是不匹配,所以搜索词还得后移一位,直到能够匹配搜索词的第一个字符“A”为止。看下图:
- 接着就是比较搜索词跟被比较字符串的下一个字符了,结果很明显,匹配。看下图:
- 接着还是往下比较,什么时候停止呢?直到搜索词和被比较字符串对应的字符不匹配为止。看下图:
- 这个时候,怎么操作呢?当然很容易想到的一种方法就是讲整个搜索词后移一位,重新比较了。我只能说这种方式很好,可行。但是你想过没有,后移一位就会把位置移到已经比较过的地方了,重新比较一遍,看下图所示。有没有隐隐觉得这里可以优化?
- 当空格与D不匹配的时候,其实你已经知道前面的字符是“ABCDAB”。KMP的基本思想就是不要重复已经比较过的位置,可以大胆的向后移,这样不是可以提高搜索的效率了吗。
- 那怎么记录那些已经比较过了呢?可以针对搜索词,算出一张专业术语名称叫《部分匹配表》,那这张表又是如何算出来的呢?这个后面介绍,先况且知道它的用法就OK了。
- 那么已知空格和D不匹配,而且前面留个字符都比较过,匹配的。可以查表得出,最后一个匹配字符B对应的“部分匹配值”是2,我就用下面的公式算法算出向后移动的位数:移动位数=已匹配的字符数-对应表的部分匹配值,所以6-2=4,后移4位。看下图:
- 因为空格和C是不匹配的,所以还要继续往后移动。利用算法算出移动位数:2-0=2 。看下图:
- 同样的道理,后移。看图:
- 同样的道理,继续后移:6-2=4位。看下图:
- 最后惊喜的发现所有的都匹配上了,于是整个搜索过程就完成了。如果字符串够长,需要找出全部匹配,那也是同样的道理,移动位数:7-0=7位,这里不再赘述了。
可能很多童鞋会说,这张表的如果算出来的,还是没有讲,那接下来我们就来讲下《部分匹配表》的产生。
首先灌输大家两个概念:“前缀”和“后缀”。前者的意思是除了最后一个字符以外,一个字符串的全部头部组合;后者的意思是除了第一个字符以外,第一个字符串的全部尾部组合,如果还不能理解,自行看下图:
《部分匹配表》就是“前缀”和“后缀”的最长的公共元素的长度。如果还不能理解,请自行看下图:
个人理解,引入这张表的意义就是字符串的头部和尾部如果有重复,需要通过这种手段找出来,不让匹配的时候错过重复的部分。
总结
怎么样?童鞋们理解了吗,总结八个字就是“后移匹配,跳过重复”。今天的文章就到这里,谢谢大家支持,下期文章再见!