講講KMP好了

所謂的KMP，想要解決的問題如下：

給你兩個字串： A 和 B，問B是否為A的子字串？
（長度為 n 和 m）

於是你想到了一個爛作法（他有一個帥氣的名字叫naive啥鬼的）：

枚舉所有在A上的起點，一一比對，看有沒有跟B一樣
時間複雜度：O( (n-m+1)*m )

這裡呢，我要奉上一個超讚的演算法，由罩神Knuth和他的夥伴所創出的KMP算法。

時間複雜度：O( n+m )

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝廢話到這裡結束

先想想在爛作法中的一些智障缺點，你像下圖這樣比對了一段，但在後面發現你們並沒有辦法在這樣繼續下去了，你把下面的B向後移了一格，又要像剛剛那樣再試一次。

但事實上你已經比對過後面的那些了，這時候，如果可以 O(1) 知道要擺在下面四個位置的哪一個（如果可以還是要選第一個），這樣就不用再一次的重新比較剛剛比過的『灰色箭頭部分』。如此便可以很順利的跑過 n 個字母，並順利的以O(n)結束掉。

其實剛剛你想要瞬間知道的就是，對於B字串，以『直線＋兩顆點點』做結尾的所有後綴，哪一個可以和B的前綴完全相合（且合的越多越好）。

所以我們假設以 i 作結尾的後綴，最長可以和以 G[i] 做結尾的前綴相合。

當我們知道G[1]~G[i]，可否推出G[i+1]呢？來討論一下：

假如B[i+1] == B[G[i]+1]，那你就知道，G[i+1] = G[i]+1。

否則：去試B[G[G[i]]+1]，再不行就是B[G[G[G[i]]]+1]，試到ok 或 試到沒得試了（也就是0）

聽完之後，你想想可能會問為什麼不是O(m^2)，但你知道G只會增加一，最多加到m，所以扣也只能扣m，整體來看就是O(m)。（前面的也是相同的情況）

code: http://codepad.org/JhbPTUVc