看完这篇文章,KMP算法再也难不到你

作者:神秘网友 发布时间:2020-09-08 15:15:13

看完这篇文章,KMP算法再也难不到你

看完这篇文章,KMP算法再也难不到你

串的模式匹配

? KMP算法

所谓模式匹配,就是求子串(又称模式串)在主串中的位置。比如

	求模式串abc在主串abcefg中的位置

很显然,是前三位。
? 很容易就想到一个时间复杂度为O(mn)的算法去匹配。

从第一个元素开始,不断匹配子串和主串是否相等
直到子串到达最后。
否则,从主串的第二个位置开始。

实现如下图:
看完这篇文章,KMP算法再也难不到你
? 而这种方式,很明显存在一个回溯的缺点(即主串的指针要回到头),每次都要回到头部,有很多重复的比较,如果可以简化掉不必要的比较,匹配速度就会大大加快。
? 比如,如果一部分之前是匹配的,且这部分这个子串中只有这么一份,如abc作为模式串,如果ab在某次匹配中已经成功匹配,但是到了c出了问题,导致整个都不匹配了。很明显,由于ab在abc中仅有一份,且又因为它之前ab匹配成功。当ab后移一位,必然匹配不成功。(因为之前的主串的位置上匹配的是ab啊)

看完这篇文章,KMP算法再也难不到你
? ? ? ? ? ? ? 原来这么简单

? 那之前提出过的,仅有一份的概念,是不是很像之前提到过的,前缀表达式。前缀表达式可以确定唯一一份的概念,于是KMP算法的核心就是利用前缀表达式+后缀表达式去掉重复的匹配的过程。他将前缀表达式和后缀表达式用一个概念叫做next数组来替换掉。

next数组

? 讲next数组之前,什么是next数组

之前的匹配算法中,子串永远是移动一位
那KMP算法需要移动几位呢:
答:		移动位数 = 已匹配的字符数-对应部分匹配值

这个对应部分的匹配值,就是next数组。

?来看张图:

看完这篇文章,KMP算法再也难不到你

根据我们上面的公式:

	移动位数=已匹配的字符数 - 对应的部分匹配值

对于上图这种情况,已经匹配了两个字符,对应的next数组,
next[3] = 0
因此

移动位数 = 2 - 0  
	 	= 2

然后得到如下图所示的情况。开始第二次匹配
看完这篇文章,KMP算法再也难不到你
第二次匹配直到
看完这篇文章,KMP算法再也难不到你

此时,
移动位数 
  =  已经匹配的字符数(4) - 对应的部分匹配值(next[4])
  =  4 - 1
  =  3
  所以将子串向后移动三位,继续匹配、

看完这篇文章,KMP算法再也难不到你
很明显,这轮结束就匹配成功了。这样我们的时间复杂度就会降低到O(m+n)。

如何求next数组?

? 我认为,next数组本质上就是本质上就是求子串中公共元素的最大长度。那我们只需要将子串的所有前缀数组和后缀数组都列写出来,求一遍即可。
比如

eg:求子串	{ a b a b a } 的next数组
 	'a': 
 			前缀{?} 
 			后缀 {?}  
 			最长前后缀长度=0
 	'ab':
 			前缀为{a}    
 			后缀{b}  
 			最长前后缀长度 = 0
 	'aba':
 			前缀为{a、ab}   
 			后缀  {a、ba}  (注意是ba不是ab)
 			最长前后缀长度 = 1     			{a}
 	'abab':
 			前缀{a、ab、aba}
 			后缀{b、ab、bab}
 			最长前后缀长度 = 2        	    {ab}
 	'ababa':
 		    前缀{a、ab、aba、abab}
 			后缀{a、ba、aba、baba}
 			最长前后缀长度 = 3 				{aba}

因此看完这篇文章,KMP算法再也难不到你
当我们在实际写程序的时候,要移动了往往是if判断不匹配之后,要得到之前匹配的个数,往往是处理If的前一位。因此,为了方便起见,我们往往将next数组整体向右移动一位。
看完这篇文章,KMP算法再也难不到你
有时候为了代码简洁,还会遇到整体+1的情况:
看完这篇文章,KMP算法再也难不到你

看完这篇文章,KMP算法再也难不到你相关教程

  1. 创建多线程两种方式
  2. 一篇文章搞定 Android动画
  3. 2020-09-07
  4. 四层负载均衡
  5. https
  6. 看完源码记不住掌握这套方法Alibaba不会少你一个工位
  7. 理解JVM运行时数据区域看这一篇文章就够了
  8. 【机器学习】多项式回归