Knuth–Morris–Pratt KMP 字串匹配演算法 — 完整教材

適用對象：演算法初學者到中階；含完整理論、6 個手動推演例子、可編譯的 C++ 程式碼，以及進階應用。

---

目錄

1. 問題定義與動機
2. 暴力法回顧與瓶頸
3. KMP 的核心觀念
4. LPS / Failure Function 的定義
5. LPS 陣列的建構演算法
6. KMP 搜尋演算法
7. 複雜度分析（含攤銷分析）
8. 六個完整手動推演例子 - 例 1：經典例子 - 例 2：高度重複字元 - 例 3：完全不匹配 - 例 4：重疊匹配 - 例 5：DNA 序列搜尋 - 例 6：英文句子搜尋
9. 完整 C++ 程式碼
10. 進階應用
11. 與其他演算法的比較
12. 練習題

---

1. 問題定義與動機

字串匹配問題（String Matching / Pattern Searching）：

給定一段文字 T（長度 N）與一個模式串 P（長度 M），找出 P 在 T 中所有出現的起始位置。

應用場景：

• 文字編輯器的「尋找/取代」功能。
• 搜尋引擎與爬蟲的關鍵字比對。
• 網路入侵偵測（IDS）中對惡意 payload 的辨識。
• 生物資訊學中的 DNA、RNA、蛋白質序列比對。
• 編譯器、語法解析器中的 token 偵測。

KMP 演算法（Knuth, Morris, Pratt 於 1977 年提出）將最壞時間複雜度從暴力法的 O(N X M) 降到 O(N + M)，且 text 的指標永不回退，是所有字串匹配演算法的入門經典。

---

2. 暴力法回顧與瓶頸

2.1 暴力法做法

對 i = 0, 1, \ldots, N - M：逐字元比對 text[i..i+M-1] 與 pattern[0..M-1]，若全部相等則記下位置。

for (int i = 0; i + m <= n; ++i) {
    int j = 0;
    while (j < m && text[i + j] == pattern[j]) ++j;
    if (j == m) cout << "Match at " << i << "\n";
}

2.2 為什麼會慢？

考慮 text = "AAAAAAAAAB"、pattern = "AAAAB"：

i=0: AAAAA vs AAAAB → 比 5 次, 第 5 次失敗
i=1: AAAAA vs AAAAB → 比 5 次, 第 5 次失敗
...
i=5: AAAAB vs AAAAB → 比 5 次, 全中

每個 i 幾乎都比對 M 次，總共 O(N X M)。

2.3 瓶頸所在

暴力法在比對失敗時，完全丟棄了之前已成功比對的資訊，每次只把 text 指標前進 1 格。

text:    A B A B A B C ...
pattern: A B A B C
                 ↑ 在 j=4 失敗
暴力法：把 i 從 0 移到 1，重新開始
但是   ：我們已經知道 text[2..3] = "AB" = pattern[0..1]，根本不必重比！

KMP 的目標：利用 pattern 自身的結構（前綴 = 後綴的關係），把 j 跳到正確的位置，而 i 永不回退。

---

3. KMP 的核心觀念

當在 pattern[j] 處比對失敗時，pattern[0..j-1] 已經匹配成功；我們可以利用 pattern 內部的「前綴等於後綴」關係，把 j 跳到較小的位置 k，繼續比對 text[i] 與 pattern[k]。

關鍵觀察：

1. text 指標 i 永遠不回退，每個字元最多被「視察」常數次。
2. pattern 指標 j 由一張預先建好的表（LPS 陣列 / failure function）來決定要跳到哪。
3. 預處理（建 LPS）需要 O(M)；搜尋需要 O(N)；總時間 O(N + M)。

---

4. LPS / Failure Function 的定義 (Longest Proper Prefix-Subfix)

4.1 「真前綴」與「真後綴」

對字串 S：

• 真前綴 (proper prefix)：S 的前綴，但不等於 S 本身（也不能是空字串才有意義，但慣例上空字串也算）。
• 真後綴 (proper suffix)：S 的後綴，但不等於 S 本身。

例如 S = \text{"ABAB"}：

真前綴	真後綴
A, AB, ABA	B, AB, BAB

兩者都包含 AB → 最長相等的真前綴 = 真後綴長度為 2。

4.2 LPS 陣列定義

對 pattern P[0..M-1]，定義 LPS 陣列（Longest Proper Prefix which is also Suffix）：

\text{lps}[j] = pattern[0..j] 的「最長相等真前綴與真後綴」的長度。

別名：failure function、partial match table、\pi 函數、next 陣列。

4.3 範例：pattern = "ABABCABAB"

j	P[0..j]	真前綴/真後綴中最長相等者	lps[j]
0	A	（空）	0
1	AB	（無）	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABC	（無）	0
5	ABABCA	A	1
6	ABABCAB	AB	2
7	ABABCABA	ABA	3
8	ABABCABAB	ABAB	4

j:        0  1  2  3  4  5  6  7  8
pattern:  A  B  A  B  C  A  B  A  B
lps:      0  0  1  2  0  1  2  3  4

4.4 LPS 在搜尋中的意義

當在 pattern[j] 失敗時：

• pattern[0..j-1] 已匹配 → 對應 text[i-j..i-1]。
• lps[j-1] 告訴我們 pattern[0..j-1] 的最長前綴 = 後綴的長度 k。
• 由於該後綴 = text[i-k..i-1]，且該後綴又等於 pattern[0..k-1]，所以可以直接讓 j 跳到 k 繼續比對 text[i]，不必回退 i。

---

5. LPS 陣列的建構演算法

5.1 演算法（兩個指標 i, len）

lps[0] = 0
len = 0       # 目前已匹配的最長前綴長度
i = 1
while i < M:
    if pattern[i] == pattern[len]:
        len = len + 1
        lps[i] = len
        i = i + 1
    else:
        if len > 0:
            len = lps[len - 1]   # 沿失敗鏈回退（不要 i++）
        else:
            lps[i] = 0
            i = i + 1

精髓：讓 pattern 自己跟自己做 KMP 匹配。

5.2 完整推演：pattern = "ABABCABAB"

初始 lps = [0,?,?,?,?,?,?,?,?]、len = 0、i = 1。

步	i	len	P[i]	P[len]	動作	lps 更新
1	1	0	B	A	不等，len==0 → lps[1]=0, i=2	[0,0,?,?,?,?,?,?,?]
2	2	0	A	A	相等 → len=1, lps[2]=1, i=3	[0,0,1,?,?,?,?,?,?]
3	3	1	B	B	相等 → len=2, lps[3]=2, i=4	[0,0,1,2,?,?,?,?,?]
4	4	2	C	A	不等，len>0 → len = lps[1] = 0	—
5	4	0	C	A	不等，len==0 → lps[4]=0, i=5	[0,0,1,2,0,?,?,?,?]
6	5	0	A	A	相等 → len=1, lps[5]=1, i=6	[0,0,1,2,0,1,?,?,?]
7	6	1	B	B	相等 → len=2, lps[6]=2, i=7	[0,0,1,2,0,1,2,?,?]
8	7	2	A	A	相等 → len=3, lps[7]=3, i=8	[0,0,1,2,0,1,2,3,?]
9	8	3	B	B	相等 → len=4, lps[8]=4, i=9	[0,0,1,2,0,1,2,3,4]

最終：lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]。

5.3 為什麼回退到 lps[len-1]？

當 pattern[i] ≠ pattern[len] 時，我們已經知道 pattern[0..len-1] 是 pattern[i-len..i-1] 的一個前綴匹配。要找下一個更短、仍可能延伸成功的前綴長度，正是 lps[len-1]（pattern[0..len-1] 第二長的前綴=後綴）。這是 KMP 的「自我相似性」核心。

---

6. KMP 搜尋演算法

6.1 主程式

i = 0     # text 指標，永不回退
j = 0     # pattern 指標
while i < N:
    if text[i] == pattern[j]:
        i = i + 1
        j = j + 1
        if j == M:
            report match at position (i - M)
            j = lps[j - 1]      # 繼續尋找下一個匹配
    else:
        if j > 0:
            j = lps[j - 1]      # 利用 LPS 跳轉，i 不動
        else:
            i = i + 1            # j 已是 0，只能讓 i 前進

6.2 不變量

• 任何時刻：text[i-j..i-1] == pattern[0..j-1]。
• text 指標 i 嚴格不減。
• pattern 指標 j 可能減少（沿 LPS 鏈），但每次減少都至少前面成功匹配過一次（攤銷分析）。

---

7. 複雜度分析（含攤銷分析）

7.1 LPS 建構：O(M)

外層 i 從 1 增至 M，至多 M 次「成功匹配」。每次「失敗回退」都讓 len 嚴格減少。由於 len 最多增 M 次，所以總減少次數也至多 M 次。總操作 \le 2M = O(M)。

7.2 搜尋：O(N)

• 「成功比對」的迴圈次數至多 N（i 每次 +1）。
• 「失敗回退」每次讓 j 嚴格減少；j 最多增 N 次（每次成功比對 +1），所以減少也至多 N 次。
• 總操作 \le 2N = O(N)。

7.3 空間複雜度

LPS 陣列佔 O(M)；搜尋本身 O(1)。總空間 O(M)。

階段	時間	空間
預處理 LPS	O(M)	O(M)
搜尋	O(N)	O(1)
整體	O(N+M)	O(M)

---

8. 六個完整手動推演例子

以下表格中，「動作」欄使用簡寫：

• MATCH：text[i] == pattern[j]，兩個指標皆 +1。
• FAIL→jump：text[i] ≠ pattern[j] 且 j > 0，跳轉 j = lps[j-1]，i 不動。
• FAIL→i++：text[i] ≠ pattern[j] 且 j == 0，僅 i 前進。
• HIT：j == M，記錄一次成功匹配，並令 j = lps[j-1]。

例 1：經典例子

text    = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

Step 1：建 LPS

j	pattern[j]	lps[j]
0	A	0
1	B	0
2	A	1
3	B	2
4	C	0
5	A	1
6	B	2
7	A	3
8	B	4

Step 2：搜尋推演

步	i	text[i]	j	pattern[j]	動作
1	0	A	0	A	MATCH → i=1, j=1
2	1	B	1	B	MATCH → i=2, j=2
3	2	A	2	A	MATCH → i=3, j=3
4	3	B	3	B	MATCH → i=4, j=4
5	4	D	4	C	FAIL→jump j = lps[3] = 2
6	4	D	2	A	FAIL→jump j = lps[1] = 0
7	4	D	0	A	FAIL→i++ → i=5
8	5	A	0	A	MATCH → i=6, j=1
9	6	B	1	B	MATCH → i=7, j=2
10	7	A	2	A	MATCH → i=8, j=3
11	8	C	3	B	FAIL→jump j = lps[2] = 1
12	8	C	1	B	FAIL→jump j = lps[0] = 0
13	8	C	0	A	FAIL→i++ → i=9
14	9	D	0	A	FAIL→i++ → i=10
15	10	A	0	A	MATCH → i=11, j=1
16	11	B	1	B	MATCH → i=12, j=2
17	12	A	2	A	MATCH → i=13, j=3
18	13	B	3	B	MATCH → i=14, j=4
19	14	C	4	C	MATCH → i=15, j=5
20	15	A	5	A	MATCH → i=16, j=6
21	16	B	6	B	MATCH → i=17, j=7
22	17	A	7	A	MATCH → i=18, j=8
23	18	B	8	B	MATCH → i=19, j=9 == M, HIT @ index 19−9 = 10

結果： 在 text 的索引 10 找到一次匹配。

---

例 2：高度重複字元

text    = "AAAAAAAAAB"     (9 個 A 接 1 個 B，共 10 字元)
pattern = "AAAAB"          (4 個 A 接 1 個 B，共 5 字元)

這是暴力法的最壞情境，但 KMP 仍是線性時間。

Step 1：建 LPS

j	pattern[j]	lps[j]
0	A	0
1	A	1
2	A	2
3	A	3
4	B	0

Step 2：搜尋推演（節錄關鍵步驟）

步	i	text[i]	j	pattern[j]	動作
1	0	A	0	A	MATCH → i=1, j=1
2	1	A	1	A	MATCH → i=2, j=2
3	2	A	2	A	MATCH → i=3, j=3
4	3	A	3	A	MATCH → i=4, j=4
5	4	A	4	B	FAIL→jump j = lps[3] = 3
6	4	A	3	A	MATCH → i=5, j=4
7	5	A	4	B	FAIL→jump j = lps[3] = 3
8	5	A	3	A	MATCH → i=6, j=4
9	6	A	4	B	FAIL→jump j = lps[3] = 3
10	6	A	3	A	MATCH → i=7, j=4
11	7	A	4	B	FAIL→jump j = lps[3] = 3
12	7	A	3	A	MATCH → i=8, j=4
13	8	A	4	B	FAIL→jump j = lps[3] = 3
14	8	A	3	A	MATCH → i=9, j=4
15	9	B	4	B	MATCH → i=10, j=5 == M, HIT @ index 10−5 = 5

結果： 索引 5 處匹配。

重點觀察： 即使重複字元極多，i 仍從 0 線性前進到 10，總操作 O(N)；暴力法在此情境下需要約 N \cdot M 次比較。

---

例 3：完全不匹配

text    = "ABCDEFGHIJ"
pattern = "XYZ"

Step 1：建 LPS

j	pattern[j]	lps[j]
0	X	0
1	Y	0
2	Z	0

Step 2：搜尋推演

步	i	text[i]	j	pattern[j]	動作
1	0	A	0	X	FAIL→i++ → i=1
2	1	B	0	X	FAIL→i++ → i=2
3	2	C	0	X	FAIL→i++ → i=3
…	…	…	0	X	…（皆相同）
10	9	J	0	X	FAIL→i++ → i=10

結果： 找不到任何匹配。共比較 10 次，呈線性。

---

例 4：重疊匹配

text    = "ABABABABAB"     (5 次 "AB" = 10 字元)
pattern = "ABAB"           (4 字元)

預期會出現多個重疊匹配。

Step 1：建 LPS

j	pattern[j]	lps[j]
0	A	0
1	B	0
2	A	1
3	B	2

Step 2：搜尋推演

步	i	text[i]	j	pattern[j]	動作
1	0	A	0	A	MATCH → i=1, j=1
2	1	B	1	B	MATCH → i=2, j=2
3	2	A	2	A	MATCH → i=3, j=3
4	3	B	3	B	MATCH → i=4, j=4 == M, HIT @ 0; j = lps[3] = 2
5	4	A	2	A	MATCH → i=5, j=3
6	5	B	3	B	MATCH → i=6, j=4 == M, HIT @ 2; j = lps[3] = 2
7	6	A	2	A	MATCH → i=7, j=3
8	7	B	3	B	MATCH → i=8, j=4 == M, HIT @ 4; j = lps[3] = 2
9	8	A	2	A	MATCH → i=9, j=3
10	9	B	3	B	MATCH → i=10, j=4 == M, HIT @ 6; j = lps[3] = 2

結果： 在索引 0, 2, 4, 6 共 4 次匹配（彼此重疊）。lps[M-1] = 2 把 j 重設成 2，正好複用了已配上的 "AB"，不必重新比對 text 任何位置。

---

例 5：DNA 序列搜尋

text    = "AGCAGCAGCAGCAG"   (14 字元)
pattern = "AGCAG"            (5 字元)

模擬基因序列中尋找重複的「motif」。

Step 1：建 LPS

j	pattern[j]	lps[j]
0	A	0
1	G	0
2	C	0
3	A	1
4	G	2

Step 2：搜尋推演

步	i	text[i]	j	pattern[j]	動作
1	0	A	0	A	MATCH → i=1, j=1
2	1	G	1	G	MATCH → i=2, j=2
3	2	C	2	C	MATCH → i=3, j=3
4	3	A	3	A	MATCH → i=4, j=4
5	4	G	4	G	MATCH → i=5, j=5 == M, HIT @ 0; j = lps[4] = 2
6	5	C	2	C	MATCH → i=6, j=3
7	6	A	3	A	MATCH → i=7, j=4
8	7	G	4	G	MATCH → i=8, j=5 == M, HIT @ 3; j = lps[4] = 2
9	8	C	2	C	MATCH → i=9, j=3
10	9	A	3	A	MATCH → i=10, j=4
11	10	G	4	G	MATCH → i=11, j=5 == M, HIT @ 6; j = lps[4] = 2
12	11	C	2	C	MATCH → i=12, j=3
13	12	A	3	A	MATCH → i=13, j=4
14	13	G	4	G	MATCH → i=14, j=5 == M, HIT @ 9; j = lps[4] = 2

結果： 索引 0, 3, 6, 9 共 4 次匹配。整個過程 i 線性掃過 14 個字元，無任何回退。

---

例 6：英文句子搜尋

text    = "she sells sea shells by the seashore"
pattern = "sea"

實作層面的小例子；展示在自然文字中的應用。為簡化，下表只列出與比對相關的關鍵步驟，其餘不匹配的 s/h/e/space/... 用「…」省略。

Step 1：建 LPS

j	pattern[j]	lps[j]
0	s	0
1	e	0
2	a	0

lps = [0, 0, 0]，因為 "sea" 沒有任何真前綴等於真後綴。

Step 2：搜尋推演（節錄）

文字索引（含空白）：

index: 0123456789...
text:  she sells sea shells by the seashore

步	i	text[i]	j	pattern[j]	動作
1	0	s	0	s	MATCH → i=1, j=1
2	1	h	1	e	FAIL→jump j = lps[0] = 0
3	1	h	0	s	FAIL→i++ → i=2
4	2	e	0	s	FAIL→i++ → i=3
5	3	(空)	0	s	FAIL→i++ → i=4
6	4	s	0	s	MATCH → i=5, j=1
7	5	e	1	e	MATCH → i=6, j=2
8	6	l	2	a	FAIL→jump j = lps[1] = 0
9	6	l	0	s	FAIL→i++ → i=7
…	…	…	…	…	（持續掃描）
	10	s	0	s	MATCH → i=11, j=1
	11	e	1	e	MATCH → i=12, j=2
	12	a	2	a	MATCH → i=13, j=3 == M, HIT @ 10; j = lps[2] = 0
…	…	…	…	…	（繼續尋找下一個 "sea"）
	28	s	0	s	MATCH → i=29, j=1
	29	e	1	e	MATCH → i=30, j=2
	30	a	2	a	MATCH → i=31, j=3 == M, HIT @ 28; j = lps[2] = 0

結果： "sea" 出現在索引 10（單詞 "sea"）與索引 28（單詞 "seashore" 的前 3 個字元）。

⚠ 注意：KMP 是「子字串比對」，不會自動處理「整字邊界」。若只要找獨立單字 "sea"，需要在匹配後額外檢查左右是否為非字母字元。

---

9. 完整 C++ 程式碼

下面是一份可直接編譯的 kmp_complete.cpp，含：

1. buildLPS — 建構 LPS 陣列。
2. kmpSearch — 回傳所有匹配位置。
3. kmpCount — 計數版本（不存位置）。
4. bruteForce — 暴力法對照。
5. shortestPeriod — 利用 LPS 求最短週期。
6. isRotation — 利用 KMP 判斷字串旋轉。
7. main — 跑遍上面 6 個範例並輸出結果。

// kmp_complete.cpp
// 編譯：g++ -std=c++17 -O2 -Wall -Wextra -o kmp_complete kmp_complete.cpp
// 執行：./kmp_complete

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> buildLPS(const string& pattern) {
    int m = static_cast<int>(pattern.size());
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            ++len;
            lps[i] = len;
            ++i;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            ++i;
        }
    }
    return lps;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> matches;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m == 0 || n < m) return matches;

    vector<int> lps = buildLPS(pattern);

    int i = 0;
    int j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            ++i;
            ++j;
            if (j == m) {
                matches.push_back(i - m);
                j = lps[j - 1];
            }
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            ++i;
        }
    }
    return matches;
}

long long kmpCount(const string& text, const string& pattern) {
    long long cnt = 0;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m == 0 || n < m) return 0;

    vector<int> lps = buildLPS(pattern);
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            ++i; ++j;
            if (j == m) { ++cnt; j = lps[j - 1]; }
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            ++i;
        }
    }
    return cnt;
}

vector<int> bruteForce(const string& text, const string& pattern) {
    vector<int> matches;
    int n = static_cast<int>(text.size());
    int m = static_cast<int>(pattern.size());
    if (m == 0 || n < m) return matches;

    for (int i = 0; i + m <= n; ++i) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) ++j;
        if (j == m) matches.push_back(i);
    }
    return matches;
}

// 應用一：利用 LPS 求字串最短週期。
// 若 m % (m - lps[m-1]) == 0，則最短週期為 m - lps[m-1]，否則整串本身是「週期」。
int shortestPeriod(const string& s) {
    int m = static_cast<int>(s.size());
    if (m == 0) return 0;
    vector<int> lps = buildLPS(s);
    int candidate = m - lps[m - 1];
    if (m % candidate == 0) return candidate;
    return m;
}

// 應用二：判斷 b 是否為 a 的旋轉。
// 經典技巧：在 a + a 中用 KMP 搜尋 b。
bool isRotation(const string& a, const string& b) {
    if (a.size() != b.size() || a.empty()) return false;
    string doubled = a + a;
    return !kmpSearch(doubled, b).empty();
}

static void printVec(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        cout << v[i];
        if (i + 1 < v.size()) cout << ", ";
    }
    cout << "]";
}

static void runCase(const string& title,
                    const string& text,
                    const string& pattern) {
    cout << "------------------------------------------------------------\n";
    cout << title << "\n";
    cout << "text    = \"" << text << "\"\n";
    cout << "pattern = \"" << pattern << "\"\n";

    vector<int> lps = buildLPS(pattern);
    cout << "LPS     = "; printVec(lps); cout << "\n";

    vector<int> kmp = kmpSearch(text, pattern);
    vector<int> bf  = bruteForce(text, pattern);
    cout << "KMP   matches = "; printVec(kmp); cout << " (count=" << kmp.size() << ")\n";
    cout << "Brute matches = "; printVec(bf);  cout << " (count=" << bf.size()  << ")\n";
    cout << (kmp == bf ? "[OK] KMP == BruteForce\n" : "[FAIL] mismatch!\n");
    cout << "\n";
}

int main() {
    runCase("Example 1: Classic",
            "ABABDABACDABABCABAB",
            "ABABCABAB");

    runCase("Example 2: Heavy repetition (worst case for brute force)",
            "AAAAAAAAAB",
            "AAAAB");

    runCase("Example 3: No match",
            "ABCDEFGHIJ",
            "XYZ");

    runCase("Example 4: Overlapping matches",
            "ABABABABAB",
            "ABAB");

    runCase("Example 5: DNA-like sequence",
            "AGCAGCAGCAGCAG",
            "AGCAG");

    runCase("Example 6: Sentence search",
            "she sells sea shells by the seashore",
            "sea");

    cout << "------------------------------------------------------------\n";
    cout << "Application 1: shortest period\n";
    for (const string& s : {string("abcabcabc"),
                            string("abcab"),
                            string("aaaaaa"),
                            string("abcdef")}) {
        cout << "  shortestPeriod(\"" << s << "\") = "
             << shortestPeriod(s) << "\n";
    }
    cout << "\n";

    cout << "------------------------------------------------------------\n";
    cout << "Application 2: string rotation\n";
    cout << "  isRotation(\"abcdef\", \"defabc\") = "
         << boolalpha << isRotation("abcdef", "defabc") << "\n";
    cout << "  isRotation(\"abcdef\", \"abcfed\") = "
         << boolalpha << isRotation("abcdef", "abcfed") << "\n";

    return 0;
}

預期輸出（節錄）

------------------------------------------------------------
Example 1: Classic
text    = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
LPS     = [0, 0, 1, 2, 0, 1, 2, 3, 4]
KMP   matches = [10] (count=1)
Brute matches = [10] (count=1)
[OK] KMP == BruteForce

Example 2: Heavy repetition (worst case for brute force)
text    = "AAAAAAAAAB"
pattern = "AAAAB"
LPS     = [0, 1, 2, 3, 0]
KMP   matches = [5] (count=1)
Brute matches = [5] (count=1)
[OK] KMP == BruteForce

Example 3: No match
text    = "ABCDEFGHIJ"
pattern = "XYZ"
LPS     = [0, 0, 0]
KMP   matches = [] (count=0)
Brute matches = [] (count=0)
[OK] KMP == BruteForce

Example 4: Overlapping matches
text    = "ABABABABAB"
pattern = "ABAB"
LPS     = [0, 0, 1, 2]
KMP   matches = [0, 2, 4, 6] (count=4)
Brute matches = [0, 2, 4, 6] (count=4)
[OK] KMP == BruteForce

Example 5: DNA-like sequence
text    = "AGCAGCAGCAGCAG"
pattern = "AGCAG"
LPS     = [0, 0, 0, 1, 2]
KMP   matches = [0, 3, 6, 9] (count=4)
Brute matches = [0, 3, 6, 9] (count=4)
[OK] KMP == BruteForce

Example 6: Sentence search
text    = "she sells sea shells by the seashore"
pattern = "sea"
LPS     = [0, 0, 0]
KMP   matches = [10, 28] (count=2)
Brute matches = [10, 28] (count=2)
[OK] KMP == BruteForce

------------------------------------------------------------
Application 1: shortest period
  shortestPeriod("abcabcabc") = 3
  shortestPeriod("abcab") = 5
  shortestPeriod("aaaaaa") = 1
  shortestPeriod("abcdef") = 6

------------------------------------------------------------
Application 2: string rotation
  isRotation("abcdef", "defabc") = true
  isRotation("abcdef", "abcfed") = false

---

10. 進階應用

10.1 字串最短週期 (Shortest Period)

對長度 M 的字串 S，令 k = M - \text{lps}[M-1]：

• 若 M \bmod k = 0，則 k 是最短週期；亦即 S 由長度 k 的子字串重複 M/k 次組成。
• 否則 M 本身（即無重複週期）就是答案。

例： "abcabcabc"，M = 9，lps[8] = 6，k = 3，9 \bmod 3 = 0 → 最短週期 3。

10.2 字串旋轉檢查

b 是 a 的旋轉 \iff b 是 a + a 的子字串。

例： a = "abcdef"、a+a = "abcdefabcdef"，搜尋 b = "defabc" → 找到於索引 3 → 旋轉成立。

10.3 字串中所有 pattern 出現次數

kmpCount 即可。常見於：

• 計算文章中某關鍵字頻率。
• 統計 DNA 中某 motif 出現次數。

10.4 多模式（簡單版）

對每個 pattern 各自跑一次 KMP：總時間 O(N \cdot k + \sum M_i)，k 為 pattern 數。若 pattern 很多，建議改用 Aho–Corasick（KMP 在 trie 上的延伸），可達 O(N + \sum M_i + \text{matches})。

10.5 KMP 自動機

可將 LPS 升級為「狀態轉移表」go[j][c] = next state，讓搜尋每步嚴格 O(1)（無 while 回退）：

vector<array<int, 26>> buildAutomaton(const string& pattern) {
    int m = (int)pattern.size();
    vector<int> lps = buildLPS(pattern);
    vector<array<int, 26>> go(m + 1);
    for (int j = 0; j <= m; ++j) {
        for (int c = 0; c < 26; ++c) {
            char ch = char('a' + c);
            if (j < m && ch == pattern[j])      go[j][c] = j + 1;
            else if (j == 0)                    go[j][c] = 0;
            else                                go[j][c] = go[lps[j - 1]][c];
        }
    }
    return go;
}

預處理 O(M \cdot |\Sigma|)，搜尋 O(N) 嚴格一次掃描。

---

11. 與其他演算法的比較

演算法	預處理	搜尋	額外空間	特色
Brute Force	—	O(NM)	O(1)	簡單，但最壞退化
KMP	O(M)	O(N)	O(M)	確定性最壞 O(N+M)，i 不回退
Z-Algorithm	O(M)	O(N)	O(N+M)	對「拼接 PT」做 Z 函數；常見於競程
Rabin–Karp	O(M)	平均 O(N+M)，最壞 O(NM)	O(1)	多 pattern、子陣列指紋很方便
Boyer–Moore	O(M+\Sigma)	平均 O(N/M)，最壞 O(NM)	O(M+\Sigma)	大型字母集（如英文）實務常用
Aho–Corasick	O(\sum M_i)	O(N + \text{matches})	O(\sum M_i)	多 pattern 同時搜尋
Suffix Array / Automaton	O(N) ~ O(N\log N)	O(M\log N)	O(N)	適合大量 pattern 對同一 text

選擇建議：

• 單一 pattern、教學或競賽 → KMP 或 Z-algorithm。
• 多 pattern 同時搜尋 → Aho–Corasick。
• 大型字母集且 pattern 較長（如英文小說搜尋）→ Boyer–Moore (Sunday)。
• 同一 text 反覆查詢不同 pattern → 後綴陣列／後綴自動機。

---

12. 練習題

完成後可用上面的 C++ 程式碼自我驗證。

1. 手動算出 pattern = "AABAACAABAA" 的 LPS 陣列，並在 text = "AABAACAADAABAACAABAA" 中找出所有匹配位置。
2. 解釋為什麼 lps[0] 一定為 0；以及 lps[i] ≤ i。
3. 證明 KMP 搜尋階段的 while 內部最多執行 2N 次（攤銷分析），給出形式化的「勢函數 (potential function)」證明。
4. 給定字串 "abcabcabcabc"，求其最短週期；推導你的計算過程。
5. 寫一段程式：給定 s 與 t，判斷是否存在某個整數 k 使得 s 旋轉 k 次後等於 t。
6. 將 KMP 改寫為「不區分大小寫」的版本（提示：先把 text 與 pattern 都轉小寫，或在比較時做轉換）。
7. 用 KMP 計算字串 "abracadabra" 中 "abra" 出現的次數（含重疊與不含重疊兩種版本）。
8. 將 KMP 升級成 KMP 自動機（見 10.5），並用它在長度 10^7 的隨機字串中搜尋 10^4 次某固定 pattern，比較執行時間。
9. 解釋為何「b 為 a 的旋轉 \iff b 是 a+a 的子字串」；請給出嚴謹的雙向證明。
10. （挑戰）將 KMP 推廣到「容許 k 個錯配」的版本，並分析時間複雜度。

---

附錄：常見錯誤與除錯提示

錯誤	症狀	解決
LPS 建構時忘記在失敗時保持 i 不動	跑出無限迴圈或錯誤 LPS	失敗回退時只改 len，不要 i++
找到匹配後忘記 j = lps[j-1]	重疊匹配（如例 4）只找到第一個	命中後一定要 j = lps[m-1]
空 pattern 未處理	runtime error / 死迴圈	一開始檢查 m == 0 或 n < m
用 int 計算大量匹配數量	溢位	改用 long long (kmpCount 範例)
搜尋時用 text[i+j] 而非 text[i]	寫成「半暴力」版，i 會回退	KMP 主迴圈只動 i 與 j

---

參考文獻

• Knuth, D. E.; Morris, J. H.; Pratt, V. R. (1977). Fast pattern matching in strings. SIAM J. Comput. 6(2): 323–350.
• Cormen, Leiserson, Rivest, Stein (CLRS) — Introduction to Algorithms, Chapter 32.
• Sedgewick & Wayne — Algorithms, 4th ed., Section 5.3.