经典算法系列：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算法原理如下图：

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