KMP演算法的實現過程

　　朴素的字元串匹配演算法的時間複雜度為O(m*n)，m、n分別為主串、模式串的長度。容易理解的是，主串和模式串的指針同步進行，當遇到不匹配的字元時，主串指針將移動到當前指針下一位，因此最壞情況下m個字元都要匹配n次。而KMP演算法能在O(m + n)的時間複雜度內完成查找，原理不再介紹，下麵介紹實現過程。

　　（1）首先在主串與模式串前均添加任一字元，使檢索時索引從1開始。

　　（2）預處理計算出next數組以免後來匹配時重覆計算。next數組的作用即當出現主串、模式串不匹配的情況時，模式串指針需要從當前位置j跳轉到next[j]的位置重新進行匹配。計算next數組的時間複雜度為O(n)，n為模式串長度。設i為計算next[i]的主索引，預設next[1] = 0直接跳過，令j = 0，i = 2。開始i++迴圈，若p[i] = p[j + 1]，則j向右一位，next[i] = j；若p[i] != p[j + 1]，此時跳轉j = next[j]，直到j = 0或p[i] = p[j + 1]時停止跳轉，若此時p[i] = p[j + 1]，重覆上一動作，next[i] = j。

int[] next = new int[n + 1];
for(int i = 2, j = 0; i <= n; i++){
        while(j > 0 && p[i] != p[j + 1]) j = next[j];
        if(p[i] == p[j + 1) j++;
        next[i] = j;
}

　　（3）計算得到next數組後進行模式匹配。設i為主串索引，j為模式串索引，令i = 1，j = 0。同樣，如果匹配失敗，則令模式串指針j跳回到next[j]處重新進行匹配，直到匹配成功時，j指針才後移。當j指針到達模式串末尾，說明匹配成功，返回true。

for(int i = 1, j = 0; i <= m; i++){
        while(j > 0 && s[i] != p[j + 1]) j = next[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n) return true;
}

　　題目見Leetcode 28. 實現strStr()。鏈接：https://leetcode-cn.com/problems/implement-strstr/。

　　實現思路：【宮水三葉】簡單題學KMP演算法。鏈接：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/。