kmp算法对于刚接触算法的朋友来说是真的一点也不友好，我也同样遭遇了它的毒打，翻阅了很多资料，终于把它弄明白了， 其中最难得就是next数组了，于是做一个next数组的总结。

话不多说，下面请观看我的表演，请戴好你的墨镜。

1、next数组是什么，这个可是kmp算法的精华，只要学会这个，其他的都是洒洒水啦。当然，这个也是最烧脑的一点。

next数组其实就是构造的前缀表，先说说这个前缀表的由来。
前缀表可以暂时理解为：字符串最长公共前缀后缀长度。这么长一串东西，请问你刚看见有什么感受。

没错，就是难搞。好吧，我肯定不能也让你难搞。
下面开始说人话。
先了解两个概念：“前缀"和"后缀”。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

下面以”ABCDABD”为例，进行介绍：
”A”的前缀和后缀都为空集，共有元素的长度为0；
”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

现在应该知道什么是字符串最长公共前缀后缀长度了吧。

接下里最重要也是最烧脑的部分来了。
接下里最重要也是最烧脑的部分来了。
接下里最重要也是最烧脑的部分来了。

现在需要构造前缀表了，也就是建立next数组。

分为三步：
1、初始化
2、前后缀的末尾不相同时怎么处理（有的文章直接就写个前后缀，让你看的一头雾水）
3、前后缀的末尾相同时怎么处理
>可能第2、3步你现在不是很理解，没事，多看下面几遍的例子

接下里看看如何实现这几步（遇见不明白的先看完例子再回来思考）

1、初始化（python代码）

#初始化一个长度为a的空数组，这个长度就是要匹配的模式串长度
next=[’’ for i in range(a)]
k=-1
next[0]=k

2、前后缀的末尾不相同时处理办法

while (k>-1 and needle[k+1]!=needle[i]):
	k=next[k]

if needle[k+1]==needle[i]:
    k+=1
next[i]=k

def getnext(self,a,needle):
        next=['' for i in range(a)]
        k=-1
        next[0]=k
        for i in range(1,len(needle)):
            while (k>-1 and needle[k+1]!=needle[i]):
                k=next[k]
            if needle[k+1]==needle[i]:
                k+=1
            next[i]=k
        return next