KMP 演算法

背景：假設有字串 s 跟比較對象 pattern，檢查是否有 pattern 存在於 s。 

目的：字串匹配時，暴力法會是每個字元 s[i] 作為起始點來看是否為 pattern，這樣的時間複雜度是 O(n*m)。

KMP 演算法藉由陣列 next 儲存 pattern 本身的「最長共同前後綴 (prefix/postfix)」來節省每次都要從頭匹配的 bottleneck，達成 O(n) 的複雜度。

最長共同前後綴：假設 pattern 為 ABABCABAB，它的 prefix 跟 postfix 可以分別為：

A, AB, ABA, ABAB, ABABC...

B, AB, BAB, ABAB, CABAB...

並且 pattern 的最長共同前後綴為 ABAB。

也就是說，假設今天比對 s 跟 pattern，然後 s[i] 開頭的子字串是 ABABF....。因為AB跟AB相同，所以可以直接滑動兩個字元，並且從第三個字元重新比較起。相對於暴力解，就不用從頭來過。

我們需要有一個陣列 next，來記錄 pattern[i] 當下的最長共同前後綴長度。以 ABABCABAB 為例的 next 為：

ABAB C ABAB

0 0 1 2 0 1 2 3 4

舉例來說，假設當 patter[7] 跟 s 不匹配，  由於 pattern[0..6] 的最長共同前後綴為 AB，下一輪將會移動兩個字元並從 pattern[2] 開始匹配。而這個 2，即為 next[6] 的 2。

要得到 next，pesudo code 如下

i 跟 j 分別想成新看得字元與舊的最長共同前後綴的下一個字元，要比較兩者是否相同。若相同，則表示最長共同前後綴長度增加；若不相同，要回頭看上一個最長共同前後綴(也就是 0..j-1)的下一個字元跟這個新字元是否相同。

1 的程式碼相對直觀，把目前比對到的 pattern 跟最長共同前後綴長度都加一並往後移一。

2跟3要處理當兩者不相同的情況。這邊想做的是回頭看上一次的最長共同前後綴，從這個看看下一個能否成立。但也不能一直回頭，如果到底了，也就是 j=0，那就只能讓next為0了。

KMP 演算法

在匹配 pattern 與字串 s 時，分別用 i, j 來記錄當下比對的位置。

當兩者相同，則 i, j 都分別向後移動1。

當兩者不同時，跟計算陣列 next 一樣，因為都需要重新調整 j (pattern) 的位置，分成 j !=0 與 j = 0 的情況。若 j 不為 0，則把 j 移到 next[j-1] 紀錄的位置，不然就是要繼續看下一個 i。

參考影片：

https://www.youtube.com/watch?v=ynv7bbcSLKE&t

https://www.youtube.com/watch?v=af1oqpnH1vA