要搞懂KPM算法，首先要了解next數(shù)組
那么，next數(shù)組到底是求什么的呢？
舉個例子，有一個字符串”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數(shù)組是什么意思呢？：
next[0],就是求a的最長相同前綴后綴，并把長度存儲進next數(shù)組；
next[1],就是求ab的最長相同前綴后綴，并把長度存儲進next數(shù)組；
next[2],就是求abc的最長相同前綴后綴，并把長度存儲進next數(shù)組；
…

next[8],就是求abcabdabc的最長相同前綴后綴，并把長度存儲進next數(shù)組。