在大學的時候，應該在資料結構裡面都看過kmp算法吧，不知道有多少老師對該算法是一筆帶過的，至少我們以前是的，
确實kmp算法還是有點饒人的，如果說紅黑樹是變态級的，那麼kmp算法比紅黑樹還要變态，很抱歉，每次打kmp的時候，輸
入法總是提示“看毛片”三個字,嘿嘿，就叫“看毛片算法”吧。
一：bf算法
如果讓你寫字元串的模式比對，你可能會很快的寫出樸素的bf算法，至少問題是解決了，我想大家很清楚的知道它的時間複
雜度為o（mn），原因很簡單，主串和模式串失配的時候，我們總是将模式串的第一位與主串的下一個字元進行比較，是以複雜
度高在主串每次失配的時候都要回溯，圖我就省略了。
二：kmp算法
剛才我們也說了，主串每次都要回溯，進而提高了時間複雜度，那麼能不能在“主串”和“模式串”失配的情況下，主串不回溯呢？
而是讓”模式串“向右滑動一定的距離，對上号後繼續進行下一輪的比對，進而做到時間複雜度為o（m+n）呢？是以kmp算法就是
用來處理這件事情的，下面我們看下簡單的例子。
通過這張圖，我們來讨論下它的一般推理，假設主串為s，模式串為p，在si != pj的時候，我們可以看到滿足如下關系式
si-jsi-j+1...sn-1=p0p1..pj-1。那麼模式p應該向右滑動多少距離？也就是主串中的第i個字元應與模式串中的哪一個字元進行比較？
假設應該與模式串中的第k的位置相比較，假如模式串中存在最大的字首真子串和字尾真子串，那麼有p0p1..pk-1=pj-kpj-k+1...pj-1.
這句話的意思也就是說，在模式p中，前k個字元與j個字元之前的k個字元相同，比如說：“abad”的最大字首真子串為“aba"，最大
字尾真子串為“bad”，當然這裡是不相等，這裡的0<k<j，我們希望k接近于j，那麼我們滑動的距離将會最小，好吧，現在我們用
next[j]來記錄失配時模式串應該用哪一個字元于si進行比較。
設 next[j]=k。根據公式我們有
-1 當j=0時
next[j] = max{k| 0<k<j 且 p0p1..pk-1=pj-kpj-k+1...pj-1}
0 其他情況
好，接下來的問題就是如何求出next[j],這個也就是kmp思想的核心，對于next[j]的求法，我們采用遞推法，現在我們知道了
next[j]=k，我們來求next[j+1]=？的問題？其實也就是兩種情況：
①：pk=pj 時 則p0p1...pk=pj-kpj-k+1...pj, 則我們知：
next[j+1]=k+1。
又因為next[j]=k，則
next[j+1]=next[j]+1。
②：pk!=pj 時 則p0p1...pk!=pj-kpj-k+1...pj,這種情況我們有點蛋疼，其實這裡我們又将模式串的比對問題轉化為了上面我們提到
的”主串“和”模式串“中尋找next的問題，你可以了解成在模式串的字首串和字尾串中尋找next[j]的問題。現在我們的思路就是一定
要找到這個k2，使得pk2=pj，然後将k2代入①就可以了。
設 k2=next[k]。 則有p0p1...pk2-1=pj-k2pj-k2+1...pj-1。
若 pj=pk2， 則 next[j+1]=k2+1=next[k]+1。
若 pj!=pk2, 則可以繼續像上面遞歸的使用next，直到不存在k2為止。
好，下面我們上代碼，可能有點繞，不管你懂沒懂，反正我懂了。
