本教材把 LPS（Longest Proper Prefix–Suffix） 與 KMP（Knuth–Morris–Pratt） 當成兩個獨立但相依的主題。 LPS 不只是 KMP 的副產物，它本身就是一個強大的字串工具；KMP 則是 LPS 最有名的應用之一。

目錄

Part A：LPS（Longest Proper Prefix–Suffix）

  1. LPS 是什麼？為什麼重要？
  2. 基本術語：前綴 / 後綴 / 真前綴 / 真後綴 / Border
  3. LPS 的形式定義
  4. 小手算：LPS 範例直觀理解
  5. LPS 的 O(N²) 笨方法
  6. LPS 的 O(N) 高效演算法
  7. 六個 LPS 完整逐步推演範例
  8. LPS 的攤還複雜度證明
  9. LPS 的獨立應用

Part B：KMP 字串匹配

  1. 字串匹配問題與暴力法
  2. KMP 的核心想法：i 不回退
  3. KMP 主演算法
  4. 四個 KMP 完整逐步推演範例
  5. 複雜度分析
  6. KMP vs 暴力法 vs Rabin–Karp vs Z-Algorithm
  7. 常見錯誤與陷阱
  8. 實際應用

Part C：C++ 完整實作

  1. LPS 完整實作
  2. KMP 完整實作
  3. 實用工具：週期、所有 Border、計數
  4. 可執行示範主程式
  5. 程式碼參照

Part A：LPS（Longest Proper Prefix–Suffix）

1. LPS 是什麼？為什麼重要？

LPS 全名 Longest Proper Prefix which is also Suffix，意為：

對於字串 (s)，找出最長的「同時是 (s) 的前綴 也是 (s) 的後綴」的子字串，但不能等於 (s) 本身。

它的別稱有：

別稱 出處
LPS 一般教科書、面試
Failure Function KMP 原論文
Partial Match Table 數位實作習慣
π 函數（pi function） CLRS、競賽社群
Border 字串學（stringology）
Next Array 中文教材常見

所有上述名稱指的是同一件事，本教材以「LPS」為主，必要時提到別名。

為什麼 LPS 這麼重要？

LPS 把字串「自我相似」的結構壓縮成一個整數陣列。有了它，你可以做：

  • KMP 字串匹配：O(N+M) 在 text 中找 pattern
  • 求字串最短重複週期：1 行運算
  • 找所有 border：O(N) 沿 LPS 鏈
  • 2 個字串的最長公共前後綴
  • AC 自動機（Aho-Corasick）：多模式匹配
  • Z-array、Suffix Automaton：許多字串結構底層都依賴前綴–後綴關係

2. 基本術語：前綴 / 後綴 / 真前綴 / 真後綴 / Border

設字串 (s = s_0 s_1 \cdots s_{n-1})。

名稱 定義 s = "ABCAB" 範例
前綴（prefix） (s[0..k])，(0 \le k \le n-1) "", A, AB, ABC, ABCA, ABCAB
後綴（suffix） (s[k..n-1])，(0 \le k \le n-1) "", B, AB, CAB, BCAB, ABCAB
真前綴（proper prefix） 前綴且 ≠ (s) 整體 "", A, AB, ABC, ABCA
真後綴（proper suffix） 後綴且 ≠ (s) 整體 "", B, AB, CAB, BCAB
Border 同時是真前綴且真後綴的字串 "", AB

⚠️ 「空字串」永遠是 border（長度 0），但通常不算「有意思」的 border。

範例：s = "ABCAB" 的所有 border

  • 真前綴："", A, AB, ABC, ABCA
  • 真後綴："", B, AB, CAB, BCAB
  • 交集："", AB
  • 最長：AB（長度 2） → LPS("ABCAB") = 2

3. LPS 的形式定義

對長度為 (n) 的字串 (s)，定義陣列 (\text{lps}[0..n-1])：

[ \text{lps}[i] \;=\; \max \bigl{\, k \;\big|\; 0 \le k \le i,\; s[0..k-1] = s[i-k+1..i] \,\bigr} ]

也就是：(s[0..i]) 的最長 border 長度。

定義邊界

  • (\text{lps}[0] = 0)（單字元無真前綴）
  • (\text{lps}[i] \le i)（border 至少要短 1 個字元）

兩種常見索引慣例

慣例 意義 本教材用法
(\text{lps}[i]) = 前綴 (s[0..i]) 的最長 border 長度 0-indexed，最常用 ✅
(\text{next}[i]) = 比對到 (s[i]) 失敗時，j 應跳到哪 中文舊教材，常 (=\text{lps}[i]-1) 或位移 1 ❌

本教材一律使用第一種慣例：lps[i] = 「以 i 結尾的前綴」的最長 border 長度。

4. 小手算：LPS 範例直觀理解

範例 4.1：s = "ABABA"

i s[0..i] 所有真前綴 所有真後綴 最長共同 lps[i]
0 A (無) (無) ε 0
1 AB A B ε 0
2 ABA A, AB A, BA A 1
3 ABAB A, AB, ABA B, AB, BAB AB 2
4 ABABA A, AB, ABA, ABAB A, BA, ABA, BABA ABA 3 
i:        0  1  2  3  4
s:        A  B  A  B  A
lps:      0  0  1  2  3

範例 4.2：s = "AAAA"（極端重複）

i s[0..i] 最長 border lps[i]
0 A ε 0
1 AA A 1
2 AAA AA 2
3 AAAA AAA 3 
i:        0  1  2  3
s:        A  A  A  A
lps:      0  1  2  3

這就是 LPS 在「全相同字元」上的形態：lps[i] = i。

範例 4.3：s = "ABCDE"（無共同前後綴）

i:        0  1  2  3  4
s:        A  B  C  D  E
lps:      0  0  0  0  0

完全沒有重複結構 → LPS 全 0。

5. LPS 的 O(N²) 笨方法

直接照定義：對每個 i，從長度 i 開始往下試，找最大的 k 使 s[0..k-1] == s[i-k+1..i]。

for i = 0 to n-1:
    lps[i] = 0
    for k = i down to 1:
        if s[0..k-1] == s[i-k+1..i]:
            lps[i] = k
            break
  • 字串相等比較：O(k)
  • 最壞每個 i 試 O(i) 種長度，每種 O(i) 比較
  • 總時間：O(N³)（簡化成 O(N²) 也行，但仍太慢）

實務上絕不使用。我們真正要學的是 O(N) 演算法。

6. LPS 的 O(N) 高效演算法

6.1 關鍵觀察

計算 (\text{lps}[i]) 時，(\text{lps}[0..i-1]) 已知。能不能利用？

是的。設 (\ell = \text{lps}[i-1])，意味 s[0..ℓ-1] == s[i-ℓ..i-1]。

現在要算 (\text{lps}[i])，看 s[i] 的角色：

  • 情況 A：s[ℓ] == s[i] → 把那個 border 延長 1 個字元 → (\text{lps}[i] = \ell + 1)。

  • 情況 B：s[ℓ] != s[i] → 縮短候選 border。下一個候選長度是 (\text{lps}[\ell-1])。 → 持續沿 LPS 鏈往下跳，直到匹配或 ℓ=0。

6.2 演算法

buildLPS(s):
    n = len(s)
    lps = array of size n, all zero
    j = 0                       # 目前候選 border 長度
    for i = 1 to n-1:
        while j > 0 and s[i] != s[j]:
            j = lps[j-1]        # 沿 LPS 鏈回退
        if s[i] == s[j]:
            j = j + 1
        lps[i] = j
    return lps

6.3 「沿 LPS 鏈回退」是什麼意思？

如果 s[0..i-1] 的最長 border 長度是 (\ell)，但 s[ℓ] != s[i]，那「次長」border 的長度是多少？

答：lps[ℓ-1]。

為什麼？因為次長 border 必定也是 border 中之 border。

s[0..i-1]  =  [—— ℓ 長 border ——]  ...  [—— ℓ 長 border ——]
                  ↑                          ↑
                 同樣字串                    同樣字串

次長 border = 在 ℓ 長 border 內部再找 border
            = lps[ℓ - 1]

這個觀察就是 LPS 為何 O(N) 的關鍵。

6.4 圖示理解

i:    0  1  2  3  4  5  6  7  8
s:    A  B  A  B  A  B  C  A  B

要算 lps[5]:
  j = lps[4] = 3   (s[0..2]="ABA" 是 s[2..4]="ABA" 的副本)
  s[j=3]='B' == s[i=5]='B'  → j=4 → lps[5] = 4

要算 lps[6]:
  j = lps[5] = 4   (s[0..3]="ABAB" = s[2..5]="ABAB")
  s[j=4]='A' != s[i=6]='C'  → j = lps[3] = 2
  s[j=2]='A' != s[i=6]='C'  → j = lps[1] = 0
  s[j=0]='A' != s[i=6]='C'  → 停止 (j=0)
  → lps[6] = 0

7. 六個 LPS 完整逐步推演範例

每個範例都會展示每次迭代的 j、while 迴圈跳轉、最終 lps 值。

範例 7.1：s = "ABABCABAB"（KMP 經典例子）

i s[i] j（進入時） while 過程 s[j]==s[i]? j（離開時） lps[i]
1 B 0 (j=0 不進迴圈) s[0]='A' ≠ 'B' 0 0
2 A 0 — s[0]='A' = 'A' → j++ 1 1
3 B 1 — s[1]='B' = 'B' → j++ 2 2
4 C 2 s[2]='A'≠'C' → j=lps[1]=0；s[0]='A'≠'C' 停 否 0 0
5 A 0 — s[0]='A' = 'A' → j++ 1 1
6 B 1 — s[1]='B' = 'B' → j++ 2 2
7 A 2 — s[2]='A' = 'A' → j++ 3 3
8 B 3 — s[3]='B' = 'B' → j++ 4 4 
i:    0  1  2  3  4  5  6  7  8
s:    A  B  A  B  C  A  B  A  B
lps:  0  0  1  2  0  1  2  3  4

範例 7.2：s = "AAACAAAAAC"

i s[i] j 進入 while s[j]==s[i]? j 離開 lps[i]
1 A 0 — 'A'='A' 1 1
2 A 1 — s[1]='A'='A' 2 2
3 C 2 s[2]='A'≠'C', j=lps[1]=1；s[1]='A'≠'C', j=lps[0]=0；s[0]='A'≠'C' 停 否 0 0
4 A 0 — 'A'='A' 1 1
5 A 1 — s[1]='A'='A' 2 2
6 A 2 — s[2]='A'='A' 3 3
7 A 3 s[3]='C'≠'A', j=lps[2]=2；s[2]='A'='A' 'A'='A' 3 3
8 A 3 s[3]='C'≠'A', j=lps[2]=2；s[2]='A'='A' 'A'='A' 3 3
9 C 3 s[3]='C'='C' 'C'='C' 4 4 
i:    0  1  2  3  4  5  6  7  8  9
s:    A  A  A  C  A  A  A  A  A  C
lps:  0  1  2  0  1  2  3  3  3  4

注意 i=7、i=8 時 j 並沒一直增加 — 它在「3」附近震盪。這正是 LPS 的微妙之處：多個 A 後不一定能延伸更長 border，因為 pattern 中間有 C 卡住。

範例 7.3：s = "AABAACAABAA"

i s[i] j 進入 while s[j]==s[i]? j 離開 lps[i]
1 A 0 — 'A'='A' 1 1
2 B 1 s[1]='A'≠'B', j=lps[0]=0；s[0]='A'≠'B' 停 否 0 0
3 A 0 — 'A'='A' 1 1
4 A 1 — s[1]='A'='A' 2 2
5 C 2 s[2]='B'≠'C', j=lps[1]=0；s[0]='A'≠'C' 停 否 0 0
6 A 0 — 'A'='A' 1 1
7 A 1 — s[1]='A'='A' 2 2
8 B 2 s[2]='B'='B' 'B'='B' 3 3
9 A 3 s[3]='A'='A' 'A'='A' 4 4
10 A 4 s[4]='A'='A' 'A'='A' 5 5 
i:    0  1  2  3  4  5  6  7  8  9 10
s:    A  A  B  A  A  C  A  A  B  A  A
lps:  0  1  0  1  2  0  1  2  3  4  5

最終 lps[10]=5 表示 s 末 5 個字元 "AABAA" 同時也是開頭 5 個字元 "AABAA"。

範例 7.4：s = "ABCDABD"

i s[i] j 進入 while match? j 離開 lps[i]
1 B 0 — s[0]='A'≠'B' 0 0
2 C 0 — 'A'≠'C' 0 0
3 D 0 — 'A'≠'D' 0 0
4 A 0 — 'A'='A' 1 1
5 B 1 — s[1]='B'='B' 2 2
6 D 2 s[2]='C'≠'D', j=lps[1]=0；'A'≠'D' 停 否 0 0 
i:    0  1  2  3  4  5  6
s:    A  B  C  D  A  B  D
lps:  0  0  0  0  1  2  0

範例 7.5：s = "ABABAB"

i s[i] j 進入 while match? j 離開 lps[i]
1 B 0 — 'A'≠'B' 0 0
2 A 0 — 'A'='A' 1 1
3 B 1 — s[1]='B'='B' 2 2
4 A 2 — s[2]='A'='A' 3 3
5 B 3 — s[3]='B'='B' 4 4 
i:    0  1  2  3  4  5
s:    A  B  A  B  A  B
lps:  0  0  1  2  3  4

最短週期 = 6 − 4 = 2（即 "AB" 重複 3 次）。

範例 7.6：s = "AAACAAAA"（while 一次跳很多步）

i s[i] j 進入 while 詳細跳法 match? j 離開 lps[i]
1 A 0 — 'A'='A' 1 1
2 A 1 — s[1]='A'='A' 2 2
3 C 2 s[2]='A'≠'C' → j=lps[1]=1；s[1]='A'≠'C' → j=lps[0]=0；s[0]='A'≠'C' 停 否 0 0
4 A 0 — 'A'='A' 1 1
5 A 1 — s[1]='A'='A' 2 2
6 A 2 — s[2]='A'='A' 3 3
7 A 3 s[3]='C'≠'A' → j=lps[2]=2；s[2]='A'='A' 'A'='A' 3 3 
i:    0  1  2  3  4  5  6  7
s:    A  A  A  C  A  A  A  A
lps:  0  1  2  0  1  2  3  3

第 i=3 觀察 while 連跳 2 次 — 這就是「沿 LPS 鏈回退」的具體表現。儘管單次回退多次，攤還下整體仍 O(N)（見 §8）。

8. LPS 的攤還複雜度證明

定理： buildLPS(s) 在長度 (n) 的字串上跑時間是 O(n)。

證明（攤還 / Amortized）

關鍵是觀察變數 j（演算法中當前候選 border 長度）的「總變化量」。

  • 每輪 i：
  • j 最多 +1（在 if (s[i]==s[j]) j++;）
  • j 可能在 while 中多次 -多步（沿 LPS 鏈回退）
  • 整個迴圈跑 (n-1) 輪，所以 j 總共 +1 至多 (n-1) 次
  • j 在任何時候不能小於 0，所以「總減量」≤「總增量」≤ (n-1)

→ while 內所有迴圈次數總和 ≤ (n-1) → 總時間 = O(n) + O(n) = O(n)

這裡用的是「信用法 / potential method」：把每次 j++ 視為「存 1 元」，每次 j 減則「花掉」。錢不能透支，故減量有界。

9. LPS 的獨立應用

LPS 不只用於 KMP！下列應用只需要 LPS 陣列。

9.1 求字串的最短週期

定理（週期定理）： 字串 (s) 的最短重複週期 (p) 滿足 (p = n - \text{lps}[n-1])。

若 (n \bmod p = 0)，則 (s) 是該週期的整數次重複。

範例：

字串 n lps[n-1] 週期 p = n − lps[n-1] n%p 結論
ABCABC 6 3 3 (ABC) 0 完全重複 2 次
ABCABCAB 8 5 3 (ABC) 2 「不完全」週期，週期是 3 但 8 不是 3 的倍數
AAAA 4 3 1 (A) 0 完全重複 4 次
ABCD 4 0 4 (ABCD) 0 沒有週期（自己）
ABABAB 6 4 2 (AB) 0 完全重複 3 次

9.2 找字串所有 border

沿 LPS 鏈一路回退，可列出 s 所有 border 的長度。

findAllBorders(s):
    L = lps[n-1]
    while L > 0:
        output L
        L = lps[L-1]

範例： s = "ABABCABAB"，lps[8]=4

L=4: 「ABAB」 是 border
L=lps[3]=2: 「AB」 是 border
L=lps[1]=0: 結束

→ s 的所有非空 border：「ABAB」、「AB」

9.3 兩字串 A、B 的最長公共前後綴

求「最長 (t) 使 (t) 是 (A) 的前綴且是 (B) 的後綴」。

做法： 對 A + '#' + B 做 LPS（# 是 A、B 中都不出現的字元），結果 lps[len-1] 就是答案。

9.4 計算字串中「重複出現」的數量

可在 KMP 內以 LPS 直接得到「pattern 在 text 中出現次數」（含重疊）。

9.5 字串自動機（AC、Suffix Automaton）

LPS 是 Aho-Corasick 自動機的 fail 指標的基礎；廣義化為「失敗連結」可處理多模式匹配。

Part B：KMP 字串匹配

10. 字串匹配問題與暴力法

10.1 問題

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

10.2 暴力法（Brute Force）

for i = 0 to N-M:
    j = 0
    while j < M and T[i+j] == P[j]: j++
    if j == M: 找到一個匹配在 i

最壞時間：O(N × M)

10.3 暴力法的死穴

T:    A A A A A A A B
P:    A A A A B
              ↑ 在 j=4 失敗

暴力法做法：i 加 1，從 T[1] 重新比對 P
但其實 T[1..3]="AAA" = P[0..2]，這資訊被丟掉了！

KMP 的核心就是不丟掉這資訊。

11. KMP 的核心想法：i 不回退

11.1 三大關鍵設計

  1. 預先計算 pattern 的 LPS 陣列
  2. text 指標 i 永不回退（每個字元最多看 1 次）
  3. 失敗時，pattern 指標 j 跳到 lps[j-1]，繼續比對

11.2 為什麼跳 lps[j-1]？

當 T[i] != P[j] 但 P[0..j-1] 已匹配時：

  • P[0..j-1] 的最長 border 長度是 lps[j-1]
  • 那個 border 既是前綴也是後綴 → text 中相同位置已有同樣字串 → 我們可以「對齊」這個 border 繼續比
T:    ... [—— lps[j-1] 長 ——] T[i]
P:    [—— lps[j-1] 長 ——] ?  ?  ...  P[j]
                          ↑
                      跳過 j - lps[j-1] 步，從 P[lps[j-1]] 繼續比 T[i]

直覺：「pattern 用自我的相似性，向右滑到下一個合理位置」。

12. KMP 主演算法

KMP_search(T, P):
    lps = buildLPS(P)
    j = 0                                    # pattern 指標
    for i = 0 to N-1:                        # text 指標 (永不回退)
        while j > 0 and T[i] != P[j]:
            j = lps[j-1]
        if T[i] == P[j]:
            j = j + 1
        if j == M:
            記錄一個匹配在 i - M + 1
            j = lps[j-1]                     # 繼續找下一個（含重疊）

兩個常見變形

變形 行為
找全部出現位置 找到一個後 j = lps[j-1] 繼續
只找第一個 找到後直接 return
計次（含重疊） counter++ 後 j = lps[j-1] 繼續
不重疊出現 找到後 j = 0、i++（跳過整個 pattern）

13. 四個 KMP 完整逐步推演範例

每個範例都標明：

  • 預計算的 LPS 陣列
  • 每一步 (i, j, T[i], P[j]) 的狀態
  • 比對結果與下一步動作

範例 13.1：T = "ABABDABACDABABCABAB"，P = "ABABCABAB"

P:        A  B  A  B  C  A  B  A  B
lps:      0  0  1  2  0  1  2  3  4
步 i T[i] j P[j] while 跳？ match? 動作
1 0 A 0 A — ✓ j=1
2 1 B 1 B — ✓ j=2
3 2 A 2 A — ✓ j=3
4 3 B 3 B — ✓ j=4
5 4 D 4 C j=lps[3]=2；P[2]='A'≠D → j=lps[1]=0；P[0]='A'≠D 停 ✗ j=0
6 5 A 0 A — ✓ j=1
7 6 B 1 B — ✓ j=2
8 7 A 2 A — ✓ j=3
9 8 C 3 B j=lps[2]=1；P[1]='B'≠C → j=lps[0]=0；P[0]='A'≠C 停 ✗ j=0
10 9 D 0 A — ✗ j=0
11 10 A 0 A — ✓ j=1
12 11 B 1 B — ✓ j=2
13 12 A 2 A — ✓ j=3
14 13 B 3 B — ✓ j=4
15 14 C 4 C — ✓ j=5
16 15 A 5 A — ✓ j=6
17 16 B 6 B — ✓ j=7
18 17 A 7 A — ✓ j=8
19 18 B 8 B — ✓ j=9 == M → 匹配！起點 = 18−9+1 = 10 
位置:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
T:      A  B  A  B  D  A  B  A  C  D  A  B  A  B  C  A  B  A  B
                                       [A  B  A  B  C  A  B  A  B]
                                       ↑ 匹配位置 10

範例 13.2：T = "AAAAAA"，P = "AA"（多個重疊匹配）

P:    A  A
lps:  0  1
步 i T[i] j P[j] match? 動作
1 0 A 0 A ✓ j=1
2 1 A 1 A ✓ j=2 == M → 匹配位置 0, j=lps[1]=1
3 2 A 1 A ✓ j=2 == M → 匹配位置 1, j=1
4 3 A 1 A ✓ j=2 == M → 匹配位置 2, j=1
5 4 A 1 A ✓ j=2 == M → 匹配位置 3, j=1
6 5 A 1 A ✓ j=2 == M → 匹配位置 4, j=1

找到 5 個匹配（含重疊）： 0, 1, 2, 3, 4

這就是 j = lps[j-1] 機制能正確處理「重疊匹配」的展示。

範例 13.3：T = "AAAAAAAAAB"，P = "AAAAB"（暴力法最壞例）

P:    A  A  A  A  B
lps:  0  1  2  3  0
步 i T[i] j P[j] while match? 動作
1 0 A 0 A — ✓ j=1
2 1 A 1 A — ✓ j=2
3 2 A 2 A — ✓ j=3
4 3 A 3 A — ✓ j=4
5 4 A 4 B j=lps[3]=3 ✓ j=4
6 5 A 4 B j=lps[3]=3 ✓ j=4
7 6 A 4 B j=lps[3]=3 ✓ j=4
8 7 A 4 B j=lps[3]=3 ✓ j=4
9 8 A 4 B j=lps[3]=3 ✓ j=4
10 9 B 4 B — ✓ j=5 == M → 匹配位置 5

比較： - 暴力法：每個 i 比 4 次失敗 + 退 1 格 → 約 4N 次比對 - KMP：i 完全不退，每次只比 1～2 次 → 線性

範例 13.4：T = "ababababab"，P = "abab"（重疊匹配）

P:    a  b  a  b
lps:  0  0  1  2
步 i T[i] j P[j] match? 動作
1 0 a 0 a ✓ j=1
2 1 b 1 b ✓ j=2
3 2 a 2 a ✓ j=3
4 3 b 3 b ✓ j=4 == M → 匹配 0, j=lps[3]=2
5 4 a 2 a ✓ j=3
6 5 b 3 b ✓ j=4 == M → 匹配 2, j=2
7 6 a 2 a ✓ j=3
8 7 b 3 b ✓ j=4 == M → 匹配 4, j=2
9 8 a 2 a ✓ j=3
10 9 b 3 b ✓ j=4 == M → 匹配 6, j=2

找到 4 個匹配（含重疊）： 0, 2, 4, 6

14. 複雜度分析

14.1 時間

階段 時間
建 LPS O(M)
搜尋 O(N)
總計 O(N + M)

證明同 §8：i、j 的「+1 次數」與「−步數」皆有界。

14.2 空間

  • LPS 陣列：O(M)
  • 結果（匹配位置）：O(K)，K = 匹配次數

14.3 與字母表大小無關

KMP 的時間複雜度與字元集大小無關（不像某些自動機方法是 O(N·|Σ|)）。

15. KMP vs 暴力法 vs Rabin–Karp vs Z-Algorithm

演算法 預處理 搜尋 空間 特點
暴力法 無 O(N·M) 最壞 O(1) 最簡單，慢
KMP O(M) O(N+M) O(M) 確定性、易理解、實作中等
Rabin–Karp O(M) 平均 O(N+M)，最壞 O(N·M) O(1) 雜湊法，可一次找多個 pattern
Z-Algorithm O(M) O(N+M) O(N+M) 與 KMP 同效率，思路不同（求 z[i]）
Boyer–Moore O(M+ Σ ) 最壞 O(N·M)，平均亞線性
Aho–Corasick O(M_total· Σ ) O(N + matches)

KMP 在「確定性線性時間 + 線性空間 + 字元集無關」之間取得了最好的平衡。

16. 常見錯誤與陷阱

  1. while 條件寫成 j >= 0 → 會在 j=0 時無限循環。正確：j > 0。
  2. lps[j-1] 寫成 lps[j] → 邏輯錯誤，得到錯的跳轉。
  3. 找到匹配後寫 j = 0 → 變成「不重疊匹配」，會漏掉重疊的匹配。
  4. i 在 while 內也加 1 → 違反「i 不回退」設計，且會跳過字元。
  5. 空 pattern / 空 text 沒處理 → lps[m-1] 在 m=0 時會越界。
  6. 以為 lps[i] 是「比對失敗時要跳到的位置」 → 那是另一種 next[i] 慣例，不要混用。
  7. 每次新 query 都重算 LPS → LPS 只跟 pattern 有關，可預先計算重複使用。

17. 實際應用

應用 用法
編輯器搜尋（Ctrl+F） 直接 KMP / Boyer-Moore
grep、ack、ripgrep 內部視長度與字元集自動切換多種匹配演算法
DNA / 蛋白質序列分析 在基因組找 motif、PCR primer 設計
網路入侵偵測（IDS / Snort） 在封包中匹配特徵碼（多用 Aho-Corasick）
Plagiarism / 抄襲檢查 找重複片段
Compiler 詞法分析 識別關鍵字
字串週期分析 利用 LPS 求最短週期
Run-Length 壓縮、字典壓縮 找重複前綴

Part C：C++ 完整實作

18. LPS 完整實作

#include <vector>
#include <string>

// 構建 LPS（Longest Proper Prefix-Suffix）陣列。
// 時間 O(N)；空間 O(N)；不依賴字元集大小。
std::vector<int> buildLPS(const std::string& s) {
    int n = (int)s.size();
    std::vector<int> lps(n, 0);
    int j = 0;                              // 當前候選 border 長度

    for (int i = 1; i < n; ++i) {
        while (j > 0 && s[i] != s[j])
            j = lps[j - 1];                 // 沿 LPS 鏈回退
        if (s[i] == s[j])
            ++j;
        lps[i] = j;
    }
    return lps;
}

帶 verbose debug 的版本（教學用）

#include <iostream>

std::vector<int> buildLPSVerbose(const std::string& s) {
    int n = (int)s.size();
    std::vector<int> lps(n, 0);
    int j = 0;

    std::cout << "建構 LPS for \"" << s << "\"\n";
    for (int i = 1; i < n; ++i) {
        std::cout << "  i=" << i << " s[i]='" << s[i] << "' j=" << j;

        while (j > 0 && s[i] != s[j]) {
            std::cout << "  → 回退 j=lps[" << j-1 << "]=" << lps[j-1];
            j = lps[j - 1];
        }
        if (s[i] == s[j]) ++j;
        lps[i] = j;

        std::cout << "  → lps[" << i << "]=" << j << '\n';
    }
    return lps;
}

19. KMP 完整實作

// 在 text 中找 pattern 的所有出現位置（含重疊）。
// 時間 O(N + M)；空間 O(M)。
std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> result;
    int n = (int)text.size();
    int m = (int)pattern.size();
    if (m == 0 || m > n) return result;

    std::vector<int> lps = buildLPS(pattern);
    int j = 0;                               // pattern 指標

    for (int i = 0; i < n; ++i) {            // text 指標 i 永不回退
        while (j > 0 && text[i] != pattern[j])
            j = lps[j - 1];
        if (text[i] == pattern[j])
            ++j;
        if (j == m) {
            result.push_back(i - m + 1);
            j = lps[j - 1];                  // 繼續找下一個（含重疊）
        }
    }
    return result;
}

變形：只找第一個出現位置（不存在回 -1）

int kmpFindFirst(const std::string& text, const std::string& pattern) {
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) return 0;
    if (m > n) return -1;

    std::vector<int> lps = buildLPS(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) j = lps[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == m) return i - m + 1;
    }
    return -1;
}

變形：計算（含重疊）出現次數

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

    std::vector<int> lps = buildLPS(pattern);
    long long cnt = 0;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) j = lps[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == m) { ++cnt; j = lps[j - 1]; }
    }
    return cnt;
}

變形：不重疊出現（each match 後跳到結尾）

std::vector<int> kmpNonOverlapping(const std::string& text, const std::string& pattern) {
    std::vector<int> res;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0 || m > n) return res;

    std::vector<int> lps = buildLPS(pattern);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) j = lps[j - 1];
        if (text[i] == pattern[j]) ++j;
        if (j == m) { res.push_back(i - m + 1); j = 0; }   // 重設
    }
    return res;
}

20. 實用工具：週期、所有 Border、計數

20.1 最短週期

int shortestPeriod(const std::string& s) {
    if (s.empty()) return 0;
    auto lps = buildLPS(s);
    return (int)s.size() - lps.back();
}

bool isPeriodic(const std::string& s) {
    int p = shortestPeriod(s);
    return p < (int)s.size() && s.size() % p == 0;
}

20.2 所有 Border 長度（由長到短）

std::vector<int> allBorders(const std::string& s) {
    std::vector<int> res;
    if (s.empty()) return res;
    auto lps = buildLPS(s);
    int L = lps.back();
    while (L > 0) {
        res.push_back(L);
        L = lps[L - 1];
    }
    return res;
}

20.3 兩個字串的最長公共前後綴

// 求最長 t 使 t 是 A 的前綴且是 B 的後綴。
int longestPrefixOfASuffixOfB(const std::string& A, const std::string& B) {
    std::string combined = A + '\x01' + B;       // \x01 為哨兵字元
    auto lps = buildLPS(combined);
    int ans = lps.back();
    if (ans > (int)A.size()) ans = (int)A.size(); // 安全裁剪
    return ans;
}

21. 可執行示範主程式

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

void printLPS(const std::string& s) {
    auto lps = buildLPS(s);
    std::cout << "s   = ";
    for (char c : s) std::cout << c << ' ';
    std::cout << "\nlps = ";
    for (int v : lps) std::cout << v << ' ';
    std::cout << "\n\n";
}

void runMatch(const std::string& T, const std::string& P) {
    std::cout << "T = \"" << T << "\"\n";
    std::cout << "P = \"" << P << "\"\n";
    auto pos = kmpSearch(T, P);
    std::cout << "找到 " << pos.size() << " 個匹配:";
    for (int p : pos) std::cout << ' ' << p;
    std::cout << "\n\n";
}

int main() {
    std::cout << "=== LPS 範例 ===\n";
    printLPS("ABABCABAB");
    printLPS("AAACAAAAAC");
    printLPS("AABAACAABAA");
    printLPS("ABCDABD");
    printLPS("ABABAB");

    std::cout << "=== KMP 範例 ===\n";
    runMatch("ABABDABACDABABCABAB", "ABABCABAB");
    runMatch("AAAAAA",               "AA");
    runMatch("AAAAAAAAAB",           "AAAAB");
    runMatch("ababababab",           "abab");

    std::cout << "=== 週期 ===\n";
    for (auto s : {"ABCABC", "ABCABCAB", "AAAA", "ABCD", "ABABAB"}) {
        std::cout << "\"" << s << "\" 週期 = " << shortestPeriod(s)
                  << "  完全週期? " << (isPeriodic(s) ? "yes" : "no") << '\n';
    }

    std::cout << "\n=== 所有 Border ===\n";
    for (auto s : {"ABABCABAB", "AAAA", "ABCD"}) {
        std::cout << "\"" << s << "\" borders: ";
        for (int b : allBorders(s)) std::cout << b << ' ';
        std::cout << '\n';
    }
    return 0;
}

編譯與執行

g++ -std=c++17 -O2 -Wall -o kmp_lps kmp_lps.cpp
./kmp_lps

22. 程式碼參照

對應的 C++ 範例檔案：

檔案 內容
kmp_algorithm.cpp KMP 完整 demo（暴力對照、verbose buildLPS、kmpSearch、shortestPeriod、6 組 test cases）

你可以基於本教材 §18–§21 的程式碼，整合成 kmp_lps.cpp 一個獨立檔案，或直接擴充既有的 kmp_algorithm.cpp。

附錄 A：常見練習題

來源 題目 用到
LeetCode 28 Find the Index of the First Occurrence in a String KMP first match
LeetCode 459 Repeated Substring Pattern LPS 週期定理
LeetCode 214 Shortest Palindrome KMP on s + '#' + reverse(s)
LeetCode 1392 Longest Happy Prefix 直接輸出 s[0..lps[n-1]-1]
LeetCode 686 Repeated String Match KMP + 週期
Codeforces 1200E Compress Words KMP merge
UVa 455 Periodic Strings LPS 週期定理
POJ 1961 Period LPS
POJ 2406 Power Strings LPS 週期

附錄 B：LPS / KMP 速查卡

LPS (build):                            KMP (search):
  j = 0                                   j = 0
  for i = 1..n-1:                         for i = 0..n-1:
      while j>0 and s[i]!=s[j]:               while j>0 and T[i]!=P[j]:
          j = lps[j-1]                            j = lps[j-1]
      if s[i]==s[j]: j++                      if T[i]==P[j]: j++
      lps[i] = j                              if j==m:
                                                  found at i-m+1
最短週期 p = n - lps[n-1]                         j = lps[j-1]
若 n%p==0 → 完全重複

參考文獻

  • Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350.
  • CLRS, Introduction to Algorithms (3rd ed.), Chapter 32.4: The Knuth-Morris-Pratt algorithm.
  • Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on Strings. Cambridge University Press.
  • Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press.