KMP算法（超容易了解的next數組求法）

我想，既然知道KMP算法了，自然對于其具體如何運作也是有一定的了解的，我也沒必要再大費口舌講廢話，大家一定查過很多資料，但是其實也都看的一知半解，好像自己懂了但是又沒有了解透，特别是next數組的求法感覺很蛋疼，那麼我就來給大家解決一下這個next數組的問題吧，如果對KMP算法沒有概念的同學請先去查清楚再過來看看。

先講一下我們後續講解的一些規範，我們next數組、以及模式串都是從數組的下标1開始儲存的，注意不是0！（這樣操作友善一點）

下面列出一個next數組：

模式串	A	B	A	B	A	B	B
j	1	2	3	4	5	6	7
next[j]	1	1	2	3	4	5

很多人可能對這個next數組的了解就是不正确的，我們來好好解釋一下：

• 第一個元素的next值，即next[1]，預設是0，這是規定的，0則表示從頭開始比較
• 那麼很多人會疑惑，那上面這個例子中，j=2的時候如果不比對，不也是應該從頭開始比較嗎？那麼為什麼next[2]不是0而是1呢？
• 好，你可能會機智地說，next[1]=0是你規定死的，而你的模式串又是從下标為1的地方儲存起來的，當然next[2] = 1啦！
• 我們知道KMP算法的比對是通過next數組慢慢往前回複（如果比對失敗的話）的一個過程，那麼經過next數組傳回後，我們究竟是從哪裡開始比較呢？是從傳回的那一個開始，還是它的前一個，亦或是後一個？
• 這就涉及對next數組的真正的了解了，我們來好好理一理，這個next數組到底是怎麼一回事！
• 所謂next數組的傳回，其實是前面有一部分是重疊的，才能這樣回退。用文字可能很難描述，我們直接拿上面的來舉例。
• j = 4的時候，這個B前面的A和第一個A是相同的，是以next[4]=2，這個2是怎麼來的呢？
• 這個2不是因為j=2的那個B，而是因為j=1的那個A，因為j=1的A和j=3的A相比對了，是以next[4] = 1 + 1，這才等于的2。等号右邊第一個1是j=1的1，第二個1是往右邊走一位的1。
• 如果夠聰明的話你應該已經看懂了，不過沒懂也沒關系，再來舉個例子，咱們看最後一個B，即​

  ​next[7]=5​

  ​​，如果你沒了解透，就會疑惑，明明j=5時是A啊！可是如果你搞明白了，就會知道​

  ​next[7]=5​

  ​​，是因為​

  ​j=3~6​

  ​​的​

  ​ABAB​

  ​​和​

  ​j=1~4​

  ​​的​

  ​ABAB​

  ​比對上了。
• 還不明白的話，咱麼可以回到​

  ​next​

  ​​數組的本質，我們在什麼時候需要使用到​

  ​next​

  ​​數組呢？不正是在第​

  ​j​

  ​個位置的元素和主串的元素不比對嗎？那麼我們就要會退到某個位置next[j]，使得第j個位置前面的元素和第next[j]個位置前面的元素要是一樣的啊！這時候我們會希望第j個位置的元素和第next[j]個位置的元素的值相同嗎？不，如果相同的話那麼一定、馬上就會要繼續查next[j]的next了，是以實際上根據這一點我們還可以對next數組進行優化，即如果第j個位置的元素和next[j]個位置的元素相等了，我們就直接讓next[j] = next[next[j]]，并且這麼一直循環下去。當然這是一種對next數組的優化了，咱們在這裡提到就行，也不細說了，能夠了解的話也知道該怎麼辦了。

那咱們看一下代碼吧、

求next數組的算法：

void getNext(Str substr, int next[])
{
    // 這個i永遠隻會往前走，而j會随着不比對而逐漸等于next[j]
    int i = 1, j = 0;
    next[1] = 0;
    while(i < substr.length)
    {
        // j=0 表示目前指向的是第一個元素
        if(j==0 || substr.ch[i] == substr.ch[j])
        {
            // 前面提到過，前面的比對，是以讓後一個等于前一個的下标+1
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}      

int KMP(Str str, Str substr, int next[])
{
    int i=1, j=1;
    while(i<=str.length && j <= substr.length)
    {
        if(j==0 || str.ch[i] == substr.ch[j])
        {
            // 這個i指向主串。是不可能退後的
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    // 如果比對成功
    if(j>substr.length) return i-substr.length;
    else return 0;
}