因為在 AppWorks School 的讀書會中負責 KMP 演算法，讀完有種一生就用這一次了的感覺，於是決定寫成文章紀念一下。
此篇內容主要講解 KMP 的原理，下一篇 KMP 演算法，從自學到放棄 (2) 則是實際程式碼的做法
此系列文章的範例程式皆會以 Javascript 呈現
以下是我參考的兩個連結，兩個都把 KMP 的概念解釋得很清楚，後續的範例也是把兩位大神的教學結合在一起講。
參考資料：
What is KMP ?
KMP 三個英文字母來源於共同發表這個演算法的三位教授名字的首字母，分別是 Knuth, Morrison 以及 Pratt，並沒有其他特別含義。
這個演算法的用途主要是透過避免持續比對相同片段來提升在一個字串中查找一個特定片段的運算效率，以下先舉個暴力比對法的例子：
假如現在有一個字串 str = “AAACAAAA”，我們要在其中尋找符合 “AAAA” 的片段，可以透過直接寫兩個 for loop 來實現。
function findPattern() {
const str = "AAACAAAA";
const pattern = "AAAA";
for (let i = 0; i < str.length - pattern.length + 1; i++) {
for (let j = 0; j < pattern.length; j++) {
// 逐一比對字母，若比對不成功則從 i+1, j = 0 重新比對
if (str[i + j] !== pattern[j]) break;
if (j === pattern.length - 1) return i;
}
}
return -1;
}從上面的程式碼中，可以很簡單的推斷出其時間複雜度為 O(N * M)，N 為 str 的長度，M 為 pattern 的長度。而 KMP 便是能將搜尋特定片段這件事優化到 O(N + M) 的演算法。
那麼該怎麼做呢？
我們先回想一下在暴力解法中，當程式在比對失敗時是怎麼運行的：
暴力解會在比對到不符合的字母時，將 pattern 整組往右移，並重新從第一個字母開始比對。這時聰明的你應該已經發現一些端倪了，當迴圈比對到第四個字母 C !== A 時，除了告訴我們第四個字母不相等以外，同時也告訴了我們另一個勵志的事實，前面三個字母都比對成功了！
那是不是有可能從已經比對成功的片段中，得知我們接下來可以從哪個位置再重新比對看看，而不需要直接從頭開始呢？
隆重介紹，LPS (Longest Prefix Suffix)
LPS (Longest Prefix Suffix) 最長相等前後綴
先簡單說明一下 prefix (前綴) 以及 suffix (後綴) 的概念：
- Prefix：一個字串從開頭開始的所有 substring，以 “AAAA” 為例，便有 “A”, “AA”, “AAA” 以及 “AAAA”。
- Suffix：一個字串從結尾開始的所有 substring，以 “AAAA” 為例，便有 “A”, “AA”, “AAA” 以及 “AAAA”。
但我們這邊要使用的是 proper prefix & suffix，prefix 以及 suffix 都不會包含其字串本身，因此 “AAAA” 並不會被納入。簡單來說，”AAAA” 這個字串的最長相等前後綴便是 “AAA”，而不會是 “AAAA”。
當我們知道了一個字串的 LPS 時，我們便能得知接下來該從哪邊開始比對了。回到前面的範例，由於已比對字串 AAA 的 LPS 為 AA，因此我們可以不重新比對 pattern 字串中的 AA，嘗試從第三個字母開始比對。
延續這個概念，我們只要先把 pattern 中每個 substring 的 LPS 求出來，便能得知當比對到某個位置失敗時，可以先回到已經成功比對的 substring 的 LPS 重新開始比對，而不總是從零開始。而用來儲存每個 substring LPS 的便是 LPS array (這是我個人的命名，網路上的中文資源大部分都稱呼其為 next 數組)。
LPS array 概念說明
LPS array 是透過動態規劃 (Dynamic Programming) 的方式，在 O(M) 的時間複雜度下找出 pattern 在該 index 時的 LPS 的長度，以作為未來比對錯誤時應該從何處開始重新比對的依據。
LPS array 具有以下兩個基本特性：
- Array 的第一個位置 (index 0) 一定為 0。
- Array 必然與 pattern 長度相等。
LPS array 中每個 index 中儲存的數字，都代表著在 pattern 中，包含該位置的字母往前的 substring 中所擁有的 LPS (最長相等前後綴)長度。
一樣以 “AAAA” 為例，他的 LPS array 會等於 [0, 1, 2, 3]。
LPS array index 0 的數值 0 的意思是，”AAAA” 這個字串中，(包含) index 0 的字母以前的 LPS 長度，因此其代表的便是 “A” 這個 substring 的 LPS。前面說明過 prefix 以及 suffix 不會包含其字串本身，所以單一字母是沒有前後綴的，也因此 LPS array 的第一個數值必定為 0。
LPS array index 1 的 1 代表的是 “AA” 這個 substring 的 LPS，也就是 1。
LPS array index 2 的 2代表的是 “AAA” 這個 substring 的 LPS，也就是 2。
以此類推…。
感謝看到這裡的你，如果你想知道實際的程式碼會如何產生出 LPS array 以及如何透過其來進行搜尋，請參考下一篇 KMP 演算法，從自學到放棄 (2)。
任何問題歡迎與我聯繫：
Email：c.s.fangyolk@gmail.com
