KMP 演算法筆記

kmp leetcode

harry xie 2025-02-09 23:31:30 ‧ 1341 瀏覽

分享至

這篇是我學習 KMP 演算法的一個紀錄。

KMP 演算法介紹

KMP（Knuth-Morris-Pratt）演算法是一種高效率的字串匹配演算法，用來在一個字串中（此文之後稱為 mainStr，文章後面，程式碼的變數也以此命名）快速搜尋一個目標字串（此文之後稱為 targetStr，文章後面，程式碼的變數也以此命名）。

它的最大特點是透過 LPS（Longest Prefix Suffix）陣列，也有些文章會稱為 next 陣列，來避免不必要的重複比較。

這個 LPS 陣列會記錄 targetStr 中每個位置的「最長可匹配前綴與後綴的長度」，當匹配失敗時，可以利用 LPS 陣列跳過已經匹配過的部分，而不需要回退到 mainStr 最起始的位置，從而提升匹配速度。

不過在舉一個 LPS 陣列當例子時，要先補充一下，如果我們嚴格區分前綴的話，其實可以分成兩種：

前綴（prefix）：可以包含整個字串本身。
真前綴（proper prefix）：不能包含整個字串本身。

這裡產生 LPS 陣列時，要採用的是真前綴。

舉例來說，假設我們的 targetStr 是 "ABABC"，則 LPS 陣列為 [0, 0, 1, 2, 0]：

位置（i）	0	1	2	3	4
字元	A	B	A	B	C
LPS 值	0	0	1	2	0

當前遍歷過的子字串為 "ABA"，前綴有 "A"、"AB"，後綴有 "A"、"BA"，共同的 LPS 為 "A"，長度 1，LPS[2] 為 1，所以 LPS 陣列中的元素值代表的是一個字串的前綴集合，和後綴集合當中，共同字串當中的最長字串的長度。
"ABAB" 的前綴 "AB" 與後綴 "AB" 是相等的，因此 LPS[3] = 2。
"ABABC" 沒有相等的前綴與後綴，所以 LPS[4] = 0。

當字串匹配失敗時，可以透過這些 LPS 值來決定 targetStr 應該向右滑動多少格，避免不必要的重複比較。

學習資源

有了前面的概念後，先不急著看程式碼，因為我自己在學習這個演算法的時候，也爬了不少文章和影片，覺得學習效果比較好的方式還是先看別人推導這個演算法的影片會比較好懂。

所以這裡推薦讀者可以先觀看 NeetCode 解說的 Knuth–Morris–Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - Python 和最浅显易懂的 KMP 算法讲解這兩部影片，再看以下的程式碼會更有概念，

靈神分享 KMP，這篇是一則短文，不過我很崇拜靈神所以把他寫的也補充上來XD。

字符串匹配 - KMP 算法原理和实现這篇是看過介紹 KMP 演算法的文章當中，最清楚的。

KMP 演算法的程式碼

這個演算法主要分成兩個部分：

1. 建立 LPS 陣列

function computeLPS(targetStr) {
    const lps = new Array(targetStr.length).fill(0);
    let prevLPS = 0;  // 目前最大前綴長度
    let i = 1; // 從 mainStr 的第二個字元開始計算

    while (i < targetStr.length) {
        if (targetStr[i] === targetStr[prevLPS]) {
            lps[i] = ++prevLPS; // 記得 prevLPS 先 + 1
            i++;
        } else {
            if (prevLPS !== 0) {
                prevLPS = lps[prevLPS - 1];  // 回溯到之前計算的 LPS 值
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

建立 LPS 陣列的時間複雜度為 O(n)，n 為 mainStr 長度。

2. 進行字串匹配

function KMPSearch(mainStr, targetStr) {
    const lps = computeLPS(targetStr);
    let i = 0; // mainStr 的 index
    let j = 0; // targetStr 的 index

    while (i < mainStr.length) {
        if (mainStr[i] === targetStr[j]) {
            i++;
            j++;
        } else {
            if (j !== 0) {
                j = lps[j - 1];  // 跳過部分匹配
            } else {
                i++;
            }
        }
        if (j === targetStr.length) {
            return i - j; // 找到匹配位置
          
            // 如果需要查找所有匹配位置，可以繼續執行，把當前位置(i - j)存在一個陣列，while 迴圈結束後回傳
            // j = lps[j - 1];
        }
    }
    return -1; // 未找到匹配
}

console.log(KMPSearch("ABABDABACDABABCABAB", "ABABCABAB")); // 10
console.log(KMPSearch("abcxabcdabcdabcy", "abcdabcy")); // 8
console.log(KMPSearch("hello world", "world")); // 6
console.log(KMPSearch("abcdef", "xyz")); // -1