最近做其他題的時候用到了KMP的算法思想，是以再寫下KMP算法的筆記增加印象。
KMP算法用于比對字元串，比起暴力優化了時間複雜度。
KMP的精髓是<code>next</code>數組。
模式串（短的那個）與主串（長的那個）比對時，若失配（<code>p[j] != s[i]</code>）時，在主串指針不動的情況（在主串指針周遊完主串之後就可以獲得整個比對的記錄）下，僅向後移動模式串指針就能夠繼續進行比對，<code>next</code>數組就記錄了模式串指針應該跳回的下标。
進一步分析，模式串指針應該跳回的下标是什麼？要跳到什麼程度才能繼續進行比對？（暴力法直接從頭開始）
失配時，目前位是不比對的，但是以前的所有位都是比對成功的。
能不能利用這一點？
模式串指針目前隻能向模式串的前方移動（同時可視作模式串相對主串向後移），移到什麼程度才能繼續進行比對？
首先要保證比對成功的最後一位還是相同的，不然沒法比啊？
同理，保證比對的倒數第二位是相同的
...
一直到移動後的模式串的首位，依然要與移動前的這個位置還是相同的，如圖
灰色線段前，模式串移動前後是自相比對的。
由于給出的條件已經保證了兩段模式串移動前後重疊的部分，是以接下來隻需要試着比對黑色部分能否比對。
若黑色部分能繼續比對，那麼繼續比對直到比對結束即可。
若不能比對，繼續前移模式串，滿足如上條件即可。
<code>next</code>數組的作用就是這樣。
暴力比對的話是需要将主串指針也向後移的，最壞情況下<code>O(n * m)</code>，是以增加了時間複雜度。
PS：其實KMP的定義也有種狀态轉換的意思，模式串指針的移動也代表了模式串指針所指向的這兩個狀态也是可以互相變換的。
先附一下代碼：
按上面的思路，如何編寫代碼，完成計算<code>next</code>數組和原主串比對這兩個任務呢？
上面的思路不僅适用于計算模式串與主串，模式串與模式串自相比對就可以得到<code>next</code>數組
假設已經知道前<code>i - 1</code>字元的<code>next</code>數組數值（圖中灰色線段前的部分），現目标是求出黑色線段所指向的第<code>i</code>個字元的<code>next</code>值。
灰色線段前的部分是相等的，對于黑色線段所指向的位置：
如果指向的部分仍是相等的，那直接就可以求出黑色線段的<code>next</code>值為：<code>next[i] = next[i - 1] + 1</code>
若不相等，繼續後移下方的模式串，直到能再次比對為止，這個過程即<code>j = i - 1, j = next[j]</code>。
至于循環條件，要麼黑線位置處相等，要麼移到頭，即<code>p[i] != p[j + 1] && j</code>
退出循環有兩種可能：
<code>p[i] == p[j + 1]</code>，則黑線部分是比對的，<code>next[i] = j + 1</code>
<code>j == 0</code>，則表表示搜到頭也沒有，即沒有可利用的前字尾重複，<code>next[i] = 0</code>
還可以發現一些可以利用的性質，<code>j</code>如果一開始賦0，它就一直代表上一個的<code>next</code>數值（第一位的<code>next</code>肯定是0），這樣我們就可以寫出求<code>next</code>的代碼
為了友善，數組從1開始
最後模式串和主串的比對同理。