在寫此文之前，我看了很多關于kmp算法的資料，此文主要是針對對應kmp算法已經稍微知道，但是卻看不懂求解next數組部分的while部分。

while部分是整個求解next數組的核心。相信看過kmp算法資料的人都知道，所謂的next數組，是待匹配的字符串的最大相同前后綴。

例如 主字符串“adhajdnjkabefaehdfbieadbkaeudio”  待匹配的字符串“adb”，就是從主串中去尋找是否存在待匹配的字符串。

對于一般情況，求解字符串的next數組，很容易理解，關鍵在于

while (index >= 0 && pattern[i] != pattern[index + 1])//pattern是待匹配的數組 ，index是對應位置的最大相同前后綴。

{index = next[index];}

我相信肯定有部分人對這個while里面的內容百思不得其解。

這里 我的next數組的初始值為0，有些資料上是-1.

如果字符串的某位的next值不為0（假設為n），說明此位（假設為y）與前面的第n位相同，并且從y-n到y，和從0到n都分別對應相同。

但是到了第y+1位時，忽然和第n+1位不一樣了，問題就來了，我一開始以為，既然不一樣了，那么y+1位的next值就是0咯。

其實不一定，因為在前n位仍然存在小于n位的字符串可能與第y+1位以及y+1位前幾位正好對應匹配。

那我們假設，存在這種情況，如下圖

倒數第二位的c和第7位的c相同。next值為7.可是倒數第1位的t和第8位的a不匹配。但是我們發現，它和第4位的t相同。并且，前面三位也正好匹配。

這確實是一種巧合，但是我們不能忽略這種巧合，關鍵在于怎么求。

我們知道，倒數第二位的c和第7位的c相同，那么如果第7位的c也有匹配值（不為0），例如圖上就是第三位的c，也就是說，倒數第二位的c和第三位的c一樣。

這個時候我們再判斷第三位和倒數第二位分別延后一位的字符是否一樣。圖上是一樣的，所以最后一位t匹配值為4.

當然，如果不一樣，我們就繼續while循環，第三位的c是否有匹配值（也就是倒數第二位的c是否還有更小的匹配值），如果有，那么重復上述。

也就是while的作用。直到前面都沒了匹配值，也就是為0了。