因為在 AppWorks School 的讀書會中負責 KMP 演算法，讀完有種一生就用這一次了的感覺，於是決定寫成文章紀念一下。
此篇內容主要講解 KMP 程式碼的做法，原理請見上一篇 KMP 演算法，從自學到放棄 (1)
此系列文章的範例程式皆會以 Javascript 呈現
以下是我參考的兩個連結，兩個都把 KMP 的概念解釋得很清楚，後續的範例也是把兩位大神的教學結合在一起講。
參考資料：
實作 LPS array
了解到 LPS array 能用來做什麼之後，接著就要來寫程式了。
以下先提供建立 LPS array 的程式碼，然後再逐步講解：
function createLPSArray(pattern) {
const lps = Array.from(pattern, () => 0);
let prev = 0, i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[prev]) {
lps[i] = prev + 1;
i++;
prev++;
} else if (prev === 0) {
lps[i] = 0;
i++;
} else {
prev = lps[prev - 1];
}
}
}- 首先定義前一個 LPS 的長度 prev 以及下一個要計算的 LPS 位置 i
- 如果比對成功便代表在 cur 這個 index 的 LPS 應該為 prev + 1，並且prev 以及 cur 都繼續往前比對。
- 若比對失敗且前一個位置 prev 已經為 0，則 lps[cur] 為 0，cur 繼續往前比對。
- 若比對失敗，且前一個位置 prev 不為 0，則代表可以透過 LPS (最長相等前後綴)來回到應該重新比對的位置。
Q1. 為什麼比對成功之後，可以直接寫 lps[cur] = prev + 1？
如果我們直接從 prev = 1, i= 2，這個位置來觀察。prev = 1 的意義是前面已經有長度為 1 的 LPS，以範例來說就代表 A (index 0) === A (index 1)。那如果現在 A (index 1)又再度等於 A (index 2) 的話，不就相當於是 A (index 0) === A (index 2) 了嗎？
換一個例子來比喻：如果今天有三個變數 a, b, c，當 a 與 b 相等，且 b 與 c 相等時，我們就可以知道 a 也會與 c 相等。
Q2. 比對失敗時的 prev = lps[prev - 1] 又是什麼意思？
回到 KMP 的核心理念，當我們比對失敗時，為了不要重頭開始，應該先掙扎一下，而 lps[prev - 1] 就是我們應該掙扎的位置。以 “AAAC” 為例，當 A (index 2) !== C (index 3) 時，別急著重頭開始比較，先回頭一看，發現 A (index 0) === A (index 2)，因此我們可以先嘗試比比看 A (index 1) 以及 C (index 3) 是否相等。以上這個例子太短了不夠明顯，我們換一個 pattern 來試試看。
換到上述的例子，當 F 與 C 不相等時，我們知道在 prev 之前的substring 都是已經比對成功的片段。於是我們透過 lps[prev - 1] 來得知該片段的 LPS 長度為 2，代表該 substring 的前兩個字母會與 i 前面的兩個字母相等，於是我們可以跳過 AB，直接從 prev = 2 與 i 做比較。
比對成功！最後一格可以填 3。
實際應用到搜尋之中
function createLPSArray(pattern) {
const lps = Array.from(pattern, () => 0);
let prev = 0, i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[prev]) {
lps[i] = prev + 1;
i++;
prev++;
} else if (prev === 0) {
lps[i] = 0;
i++;
} else {
prev = lps[prev - 1];
}
}
return lps;
}
function findPattern(str, pattern) {
const lps = createLPSArray(pattern);
let i = 0, j = 0;
while (i < str.length) {
if (str[i] === pattern[j]) {
i++;
j++;
} else {
if (j === 0) {
i++;
} else {
j = lps[j - 1];
}
}
if (j === pattern.length) return i - pattern.length;
}
return -1;
}
有沒有發現在實際搜尋時與建立 LPS array 時的相似之處。當我們比對失敗的時候，都要先透過 LPS array 找到可以重新嘗試的地方先比對看看，以避免每一次都從頭開始比對的時間浪費。
以上便是將搜尋特定字串的時間複雜度從 O(N * M) 優化至 O(N + M) 的 KMP 演算法，我會說有種一生學這一次的感覺的原因，主要是因為原本的暴力解其實也沒那麼糟拉，因為真實世界的暴力解法其實不是很常會跑到 N * M (應該)。
如果想應用看看 KMP，可以寫寫看 Leetcode 28. Find the Index of the First Occurrence in a String
任何問題歡迎與我聯繫：
Email：c.s.fangyolk@gmail.com
