模式串匹配---KMP

????????朴素的的模式串匹配算法通常要在向前移动文本指针之后，回溯模式串指针，其效率为O(m*n)，而KMP算法则挖掘了一些模式串中的一些信息，来加快匹配的效率。

??????? KMP算法的紧随便是覆盖函数next。当模式串p[j]和文本串s[i]失配时，j指针不是简单的回溯，而是指向next[j]。

??????? 覆盖函数next如何定义呢，它本质上是找到即是模式串p的前缀，又是它的后缀的最长字符串，即找到最大的k使得p[0]p[1]....p[k-1]=p[j-k]p[j-k+1]..p[j-1],然后将next[j]赋值为k。当然，这样的赋值并非最优化，注意到如果p[j]=p[k]，那next[j]和s[i]也必然失配，因此要递归的找到一个k使得p[j]!=p[k].

?????? 以下是KMP算法的代码：

??????

?
?