经典算法系列:KMP算法

网易等公司在笔试中经常会考察有关字符串的题目,因此,我们要掌握相关算法。通常这些题目会考察模式匹配,以及情况的列举,因此,本文介绍经典的KMP模式匹配算法和经典的全排列算法。下面首先介绍字符串相关知识。

假定有字符串s1,s2,strcpy(s1,s2)表示将s2赋值给s1;strcat(s1,s2)表示将s2连接到s1后面;strchr(s,c)从串s中查找字符c;strcmp(s1,s2)比较s1,s2,s1=s2返回0,s1s2返回1;StrLength(s)表示s的长度。

对于s1和s2的比较,举个例子:s1=abc,s2=abcd,则s2>s1;s1=abc,s2=abb123,则s1>s2。

模式匹配:对于主串s和子串t,在s中寻找t的过程称为模式匹配,找到返回t在s中的位置,否则返回0。

对于模式匹配,朴素的算法使BF算法,思想很简单,就是子串对主串循环遍历比较,但是这种方法有大量的重复比较,效率很低,KMP算法是对BF算法的改进。KMP算法的思想是对主串s和子串(模式)t进行模式匹配,主串中的字符只匹配一次。那么如何实现呢?如下图所示,子串t和主串s匹配,si和tj不匹配,将子串t向右移动k个单位,tk继续和si比较。

那么,这个k值是如何来的呢?为了让主串每个字符只匹配一次,KMP算法对子串进行了分析,K值只与子串有关。一般确定k值的函数为next函数。next数组的含义就是每个子串的最长前缀与最长后缀的相同长度。假设我们的子串为ababaca,那么我们对其进行分析。ababaca,长度是7,所以next[0],next[1],next[2],next[3],next[4],next[5],next[6]分别计算的是a,ab,aba,abab,ababa,ababac,ababaca的相同的最长前缀和最长后缀的长度。它们的相同的最长前缀和最长后缀分别是0,0,a,ab,aba,0,a。(注意,最长前缀不包括最后一个字符) 所以next数组的值是[0,0,1,2,3,0,1]。

现在大家该明白为何只需移动k个单位,子串就可以继续与主串匹配了吧,如上图所示,子串的3,4区域是相等的,即前缀等于后缀,所以只要子串向右移动k个单位,相等的前缀与后缀重合,无需比较,只要接着匹配tk与si即可。以上就是KMP算法的一个难点。还有一个关键是next函数的实现,这也是一大难点。实际上弄懂了next,就弄懂了KMP算法。

代码如下:

在calc_next函数中,我们拿相同的前后缀那一部分比较,k表示相同的最大前缀与最大后缀长度,如果t[k+1]==t[j],那么k++,next[j]=k,如果不相等,令k=next[k],k=next[k]是理解的难点。当t[k+1]!=t[j],我们就要对t[j]前的长度为K的后缀进行分析,看那个后缀是否有相同前后缀,如下图:

KMP算法原理如下图:

本文所有代码均为本人编写并经过测试,如有错误或问题,欢迎留言或私信指正。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180308G0L6XU00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券