KPM算法的next数组

要搞懂KPM算法，首先要了解next数组
那么，next数组到底是求什么的呢？
举个例子，有一个字符串”abc abd abc”（空格无意义）,
要求它的最长的相同前缀后缀。

所谓前缀，就是字符串中的所有字符，末尾有一个或多个字符被切断。

“S”、“Sn”、“Sna”和“Snap”都是“Snape”的前缀

所谓后缀，就是字符串中的所有字符，开头有一个或多个字符被切断。

“agrid”、“grid”、“rid”、“id”和“d”都是“Hagrid”的后缀

那么”abc abd abc”的前缀为：

{“a ”、“ab ”、“abc ”、“abca ” 、“abcab ”、“abcabd ”、“abcabda ” 、“abcabdab ”}

后缀为：

{“ c”、 “ bc”、 “ abc”、 “ dabc”、“ bdabc”、 “ abdabc”、 “ cabdabc”、“ bcabdabc” }

相同的前缀后缀有”abc”， 最长的相同前缀后缀自然也只能是”abc”，长度为3

而这个字符串的next数组是什么意思呢？：
next[0],就是求a的最长相同前缀后缀，并把长度存储进next数组；
next[1],就是求ab的最长相同前缀后缀，并把长度存储进next数组；
next[2],就是求abc的最长相同前缀后缀，并把长度存储进next数组；
…

next[8],就是求abcabdabc的最长相同前缀后缀，并把长度存储进next数组。