作者：Grey
原文位址: KMP算法解決字元串比對問題
假設字元串str長度為N，字元串match長度為M，<code>M <= N</code>, 想确定str中是否有某個子串是等于match的。傳回和match比對的字元串的首字母在str的位置，如果不比對，則傳回-1
OJ可參考：LeetCode 28. 實作 strStr()
從str串中每個位置開始比對match串，時間複雜度<code>O(M*N)</code>
KMP算法可以用<code>O(N)</code>時間複雜度解決上述問題。
我們規定數組中每個位置的一個名額，這個名額定義為
這個位置之前的字元字首和字尾的比對長度，不要取得整體。
例如: <code>ababk</code> 這個字元串，<code>k</code>位置的名額為2, 因為<code>k</code>之前位置的字元串為<code>abab</code>
字首<code>ab</code> 等于 字尾<code>ab</code>，長度為2，下标為3的<code>b</code>的名額為1，因為<code>b</code>之前的字元串<code>aba</code> ,字首<code>a</code> 等于字尾<code>a</code>, 長度為1。
人為規定：<code>0</code>位置的名額是-1，<code>1</code>位置的名額0
假設match串中每個位置我們都已經求得了這個名額值，放在了一個<code>next</code>數組中，這個數組有助于我們加速整個比對過程。
我們假設在某個時刻，比對的到的字元如下
其中str的<code>i..j</code>一直可以比對上match串的<code>0...m</code>, str中的<code>x</code>位置和match串中的<code>y</code>位置第一次比對不上。如果使用暴力方法，此時我們需要從str的<code>i+1</code>位置重新開始比對match串的<code>k</code>位置，而KMP算法，利用next數組，可以加速這一比對過程，具體流程是，依據上例，我們可以得到<code>y</code>位置的<code>next</code>數組資訊，假設<code>y</code>的<code>next</code>數組資訊是2，如下圖
如果<code>y</code>的<code>next</code>數組資訊是2，那麼<code>0...k</code> 這一段完全等于<code>f...m</code>這一段，那麼對于match來說，當<code>y</code>位置比對不上<code>x</code>位置以後, 可以直接讓<code>x</code>位置比對<code>y</code>的<code>next</code>數組位置<code>p</code>上的值，如下圖
如果比對上了，則<code>x</code>來到下一個位置，<code>p</code>來到下一個位置繼續比對，如果再次比對不上，假設<code>p</code>位置的next數組值為0, 則繼續用<code>x</code>比對<code>p</code>的<code>next</code>數組位置<code>0</code>位置上的值，如下圖
如果<code>x</code>位置的值依舊不等于<code>0</code>位置的值，則宣告本次比對失敗，str串來到<code>x</code>下一個位置，match串從<code>0</code>位置開始繼續比對。
<code>next</code>數組的求解是KMP算法中最關鍵的一步，要快速求解<code>next</code>數組，需要做到當我們求<code>i</code>位置的<code>next</code>資訊時，能通過<code>i-1</code>的<code>next</code>數組資訊加速求得,如下圖
當我們求<code>i</code>位置的<code>next</code>資訊時，假設<code>j</code>位置的<code>next</code>資訊為6，則表示
<code>m...n</code>這一段字元串等于<code>s...t</code>這一段字元，此時可以得出一個結論，如果：
<code>x</code>位置上的字元等于<code>j</code>位置上的字元，那麼<code>i</code>位置上的<code>next</code>資訊為<code>j</code>位置上的<code>next</code>資訊加1，即為7。如果不等，則繼續看<code>x</code>位置上的<code>next</code>資訊，假設為2，則有：
此時，判斷<code>q</code>位置的值是否等于<code>j</code>位置的值，如果相等，那麼<code>i</code>位置上的<code>next</code>資訊為<code>x</code>位置上的<code>next</code>資訊加1，即為3，如果不等，則繼續看<code>q</code>位置上的<code>next</code>資訊，假設為1，那麼有
此時，判斷<code>p</code>位置的值是否等于<code>j</code>位置的值，如果相等，那麼<code>i</code>位置上的<code>next</code>資訊為<code>q</code>位置上的<code>next</code>資訊加1，即為2，如果不等，則繼續如上邏輯，如果都沒有比對上<code>j</code>位置的值，則<code>i</code>位置的<code>next</code>資訊為0。
<code>next</code>數組的求解流程時間複雜度顯然為<code>O(N)</code>，現在估計主流程的複雜度，主流程中，<code>x</code>能取得的最大值為str字元串的長度N，定義一個變量<code>x-y</code>,能取得的最大值不可能超過N（即當x = N，y=0時候），在主流程的wile循環中，有三個分支
我們考慮這三個分支對于<code>y</code>和<code>y - x</code>變化範圍的影響
分支
y
y - x
x++; y++
推高
不變
x = next[x]
y++
如上分析，<code>y</code>和<code>y-x</code>都不可能降低，且三個分支隻能中一個，是以，而<code>y</code>和<code>y-x</code>的最大值均為N，所有分支執行總推高的次數不可能超過2N。即得出主流程的複雜度<code>O(N)</code>
思路
将這個字元串拼接一下, 比如原始串為：123456，拼接成：123456123456
如果比對的字元串是這個拼接的字元串的子串，則互為旋轉詞。
先将兩棵樹分别序列化為數組A和數組B，如果B是A的子串，那麼A對應的二叉樹中一定有某個子樹的結構和B對應的二叉樹完全一樣。
算法和資料結構筆記
算法和資料結構體系班-左程雲