KMP算法：字符串匹配的智慧跳躍

文章目錄

起因：暴力法的致命缺陷
- 暴力搜索的局限性
KMP核心思想：避免重復
- 理解前綴表（PMT）
- 不匹配時的回退機制
- 代碼：高效字符串匹配
- 補充：next表和PMT表
暴力法 vs KMP
總結：KMP 是如何改變游戲規則的
總結：KMP 是如何改變游戲規則的

起因：暴力法的致命缺陷

不知道你有沒有曾經為編程中的慢速字符串搜索而煩惱嗎？想象一下處理成千上萬的字符，卻發現你的解決方案運行時間過長。如果有一種方法可以極大地加快這個過程，會怎么樣呢？

偶然一次刷題中也遇到了這么一個問題，看似一道很簡單的題，背后卻又大學問，題目的描述如下：

給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標（下標從 0 開始）。如果 needle 不是 haystack 的一部分，則返回 -1 。

leetcode鏈接掛這了，有興趣的小伙伴可以去試試。[找出字符串中第一個匹配項的下標]

其實就是一個字符串匹配，剛讀完題我就想到了一個方法，原思路是這樣的：

1、以 needle 的第一個字符為基準，順序遍歷 haystack 字符串

2、如果第一個字符串相等，再以此開始，同時移動 needle 和 haystack 的下標

3、如果 needle 遍歷完則表示可以匹配到，反之則表示沒有匹配到需要繼續遍歷

4、沒有匹配到則將 haystack 的下標回到上一次匹配的下一個，needle 則回到第一個

5、重復2、3、4，如果 haystack 遍歷完都沒有匹配到，則不存在

基于此思路，寫下如下代碼：

int strStr(string haystack, string needle) 
{int n = haystack.size(), m = needle.size();if (m == 0) return 0;if (n < m) return -1;for (int i = 0; i <= n - m; i++) // 優化循環終止條件{ if (haystack[i] != needle[0]) continue;int j;for (j = 0; j < m; j++) // 直接比較字符，無需創建臨時字符串{ if (haystack[i + j] != needle[j]) break;}if (j == m) return i;}return -1;
}

暴力搜索的局限性

這種方法實現簡單，但是性能卻經不起推敲，用一組看似簡單的測試案例演示：

// 主串（haystack）: "AAAAAAAAB" （8個'A' + 1個'B'，長度9）
// 模式串（needle）: "AAAB"       （3個'A' + 1個'B'，長度4）
int pos = strStr("AAAAAAAAB", "AAAB"); // 正確結果應為5

根據代碼邏輯，實際匹配過程如下（👉 逐幀解析）：

i=0（主串起始位置）
- 比較 haystack[0]（A） == needle[0]（A） → 成功
- 逐字符檢查
  
  ：
  - j=0: A vs A ?
  - j=1: A vs A ?
  - j=2: A vs A ?
  - j=3: A vs B ?
- 總計比較4次 → 失敗，i++
i=1（主串第二個A）
- 再次比較 haystack[1]（A） == needle[0]（A） → 成功
- 逐字符檢查
  
  ：
  - j=0: A vs A ?
  - j=1: A vs A ?
  - j=2: A vs A ?
  - j=3: A vs B ?
- 總計比較4次 → 失敗，i++
  （👉 問題浮現：主串的i=1~3位置已經被驗證為A，卻再次重復比較！）
i=2、i=3、i=4、i=5
- 每次i遞增后，完全重復上述過程 → 每次比較4次，均失敗
i=6（主串第七個A）
- 比較 haystack[6]（A） == needle[0]（A） → 成功
- 逐字符檢查
  
  ：
  - j=0: A vs A ?
  - j=1: A vs A ?
  - j=2: A vs A ?
  - j=3: B vs B ?
- 總計比較4次 → 成功，返回i=5

用一張圖片來演示，如下圖：

最后的數字觸目驚心，這就是暴力法的 “重復稅”。

總比較次數 = 4（i=0） + 4（i=1） + 4（i=2） + 4（i=3） + 4（i=4） + 4（i=5） + 4（i=5） = 28次
實際有效比較：只需檢查主串i=5~8位置的"AAB"是否匹配，理想情況僅需4次比較！

🔥 核心問題：暴力法像陷入泥潭一樣，每次失敗后主串指針i僅前進1步，導致已確認匹配的字符被反復重驗。當模式串有大量重復前綴時（如本例的"AAA"），這種冗余比較會被無限放大！

當我們再換一種思維實驗：如果主串是10000個’A’加’B’？

假設 haystack = string(10000, 'A') + "B"，needle = string(999, 'A') + "B"，暴力法比較次數 ≈ (10000 - 1000) * 1000 = 9,000,000次。

暴力方法看起來簡單易懂，但效率極低。問題出現在我們找到不匹配時。我們不是跳過已經檢查過的字符，而是反復回到它們那里進行檢查，導致無數不必要的比較。怎么解決這個問題？這正是本文說要說的重點——KMP，今天，讓我們深入了解 KMP（Knuth-Morris-Pratt），這是解決這個常見問題的優雅且高效的方法。

KMP核心思想：避免重復

想象你正在搜索一個巨大的文件，并且你已經在開頭找到了一個模式匹配。使用暴力搜索，你會從非常開始的地方再次開始，反復檢查相同的點。然而，KMP 就像一個聰明的助手，它會記住你已經看過的位置，并幫助你跳過。

KMP 通過避免我們在暴力方法中看到的冗余比較來解決此問題。關鍵思想是，當發生不匹配時，我們不是將 haystack 指針向前移動一個位置，而是利用我們已經收集到的關于匹配字符的信息，移動 needle 指針。

我們如何實現這一點？通過使用前綴表（PMT）。

理解前綴表是理解KMP算法的關鍵，可以說這個前綴表就是KMP算法的核心，所以再次強調：前綴表記錄的是每個位置的最長公共前后綴的長度！

理解前綴表（PMT）

前綴表，或部分匹配表，存儲了 needle 的最長正確前綴同時也是后綴的長度，因此也叫最長公共前后綴。這有助于算法跳過已經匹配的部分 needle ，而不是從頭開始。

讓我們通過一個例子來分解它是如何工作的：

ABABAC示例：為 ABABAC 構建前綴表，以下是構建該字符串的前綴表（PMT）的方法：

步驟1：i=1（字符B）

比較pattern[1](B)與pattern[j=0](A)
不匹配 → j保持0，pmt[1]=0

步驟2：i=2（字符A）

比較pattern[2](A)與pattern[j=0](A)
匹配 → j++ → pmt[2]=j (j=1)

步驟3：i=3（字符B）

比較pattern[3](B)與pattern[j=1](B)
匹配 → j++ → pmt[3]=j (j=2)

步驟4：i=4（字符A）

比較pattern[4](A)與pattern[j=2](A)
匹配 → j++ → pmt[4]=j (j=3)

步驟5：i=5（字符C）

比較pattern[5]?與pattern[j=3](B)
不匹配 → j=pmt[j-1]=pmt[2]=1
再次比較pattern[5]?與pattern[j=1](B) → 仍不匹配
繼續回退j=pmt[j-1]=pmt[0]=0
最終pmt[5]=0

最終PMT：[0, 0, 1, 2, 3, 0]

索引	0	1	2	3	4	5
字符	A	B	A	B	A	C
PMT	0	0	1	2	3	0

在上面的動畫中，你可以看到 KMP 如何通過利用之前匹配收集到的信息來避免不必要的檢查。觀察當發生不匹配時，模式指針如何跳到前面，從而加快過程。

不匹配時的回退機制

當模式串在位置j匹配失敗時，利用PMT值跳轉到pmt[j-1]繼續匹配：

案例：主串ABABABAC vs 模式串ABABAC（PMT=[0,0,1,2,3,0]）

 主串：A B A B A B A C  
模式串：A B A B A C  
匹配失敗位置：j=5（字符C）

回退步驟：

查pmt[j-1]=pmt[4]=3
模式串跳轉到j=3（字符B）繼續與主串i=5比較
跳過冗余比較A B A（已通過PMT確認匹配）

核心代碼實現:

Cppvoid build_pmt(string pattern, vector<int>& pmt) 
{pmt[0] = 0;int j = 0;for (int i = 1; i < pattern.size(); i++) {// 關鍵回退：利用已計算的pmt值遞歸查找while (j > 0 && pattern[i] != pattern[j]) {j = pmt[j-1];}// 匹配成功則延長共同前后綴if (pattern[i] == pattern[j]) j++;pmt[i] = j;}
}

理解了回退機制，我們來看看如何用代碼實現這一邏輯。

代碼：高效字符串匹配

有了前綴表，KMP 算法可以智能地跳過之前匹配的部分。這里是 C++ 中的 KMP 實現：

void build_pmt(string pattern, vector<int>& pmt) 
{int j = 0;pmt[0] = 0;for (int i = 1; i < pattern.size(); i++) {while (j > 0 && pattern[i] != pattern[j]) {j = pmt[j - 1];}if (pattern[i] == pattern[j]) j++;pmt[i] = j;}
}int strStr(string haystack, string needle) 
{if (needle.empty()) return 0;if (needle.size() > haystack.size()) return -1;vector<int> pmt(needle.size(), 0);build_pmt(needle, pmt);int j = 0;for (int i = 0; i < haystack.size(); i++) {while (j > 0 && haystack[i] != needle[j]) {j = pmt[j - 1];}if (haystack[i] == needle[j]) j++;if (j == needle.size()) {return i - needle.size() + 1;}}return -1;
}

補充：next表和PMT表

可能有些人之前看到的代碼很多人寫的是next數組并不是pmt，并且很多都是將第一個初始化為-1。這時候可能有人會疑惑，next和pmt有關系嗎，有什么區別？

其實這并不涉及到KMP的原理，而只是工程代碼的具體實現，將第一位初始化為-1其實就是前綴表的統一右移一位后，第一位補-1。

PMT（部分匹配表）
- 定義：記錄模式串每個前綴子串的最長公共前后綴長度（不包含自身）。
- 示例：模式串ABABAC的PMT為[0,0,1,2,3,0]，表示各位置的最長公共前后綴長度
- 核心作用：通過已匹配的信息，避免主串指針回溯。
next數組
- 定義：由PMT右移一位并首位補-1得到，用于直接指示失配時模式串指針的跳轉位置。
- 示例：PMT[0,0,1,2,3,0]右移后得到next數組[-1,0,0,1,2,3]
- 核心作用：簡化代碼邏輯，避免手動計算偏移量。

在右移之后，就不需要在進行類似于 j = ptm[j - 1]，而 next[j] = ptm[j - 1]，因此就有 j = next[j]。硬要說區別的話就是兩者所表達的意義變了：

PMT：回答“當前已匹配的子串中，前后綴有多少字符是重復的？”
next數組：回答“失配時，模式串指針應跳轉到哪個位置繼續匹配？”

總的來說兩者：

本質相同：PMT和next數組的核心數據一致，均基于最長公共前后綴的復用思想。
工程優化：next數組通過右移和補-1操作，簡化了代碼實現中的指針跳轉邏輯，是PMT的工程化變體。

下面是用next表實現的代碼：

#include <vector>
using namespace std;void build_next(string pattern, vector<int>& next) 
{int n = pattern.size();next.resize(n);next[0] = -1;  // 傳統 next 數組第一個位置為 -1int j = -1;    // 為了配合 next[0] = -1，j 初始化為 -1for (int i = 0; i < n; ) {if (j == -1 || pattern[i] == pattern[j]) {i++;j++;next[i] = j;  // next[i] 對應 pmt[i-1]} else {j = next[j];  // 利用已計算的 next 回溯}}
}int strStr(string haystack, string needle) 
{if (needle.empty()) return 0;if (needle.size() > haystack.size()) return -1;vector<int> next;build_next(needle, next);int i = 0, j = 0;int n = haystack.size(), m = needle.size();while (i < n && j < m) {if (j == -1 || haystack[i] == needle[j]) {i++;j++;} else {j = next[j];  // 直接根據 next 跳轉}}return (j == m) ? i - m : -1;
}

暴力法 vs KMP

讓我們重新審視我們之前的例子，其中包含 haystack = "AAAAAAAAB" 和 needle = "AAAB" 。

暴力破解：28 次比較
KMP：僅需 9 次比較（多虧了前綴表）

當處理大量字符串時，性能差異變得更加明顯。KMP 通過利用它在匹配過程中收集的信息，有效地減少了不必要的比較次數。以下是暴力法和KMP的性能對比，隨著字符長度的增加，性能差異越來越大。

總結：KMP 是如何改變游戲規則的

KMP 通過減少冗余檢查的數量，革新了我們對字符串匹配的方法。借助前綴表，KMP 可以智能地跳過已匹配的部分，使其比暴力方法顯著更高效。下次你需要搜索子字符串時，記得 KMP 算法。這不僅僅是一種避免不必要工作的聰明方法——它還是向編寫更簡潔、更高效的代碼邁出的一大步。

嘗試在不同字符串搜索問題中實現 KMP 算法，并使用更大的數據集進行實驗。你將看到 KMP 算法的實時好處，尤其是在處理文本處理或生物信息學等應用中的大量字符串時。
得更加明顯。KMP 通過利用它在匹配過程中收集的信息，有效地減少了不必要的比較次數。以下是暴力法和KMP的性能對比，隨著字符長度的增加，性能差異越來越大。

[外鏈圖片轉存中…(img-czSr32l5-1740039479058)]