KMP算法通過構(gòu)建next數(shù)組實現(xiàn)高效字符串匹配，先預處理模式串得到最長相等前后綴信息，再利用該表在主串中跳過無效比較，最終在O(m+n)時間內(nèi)完成匹配。

在C++中實現(xiàn)KMP（Knuth-Morris-Pratt）算法，核心是通過預處理模式串生成一個部分匹配表（通常稱為next數(shù)組），利用該表在匹配失敗時跳過不必要的比較，從而提高字符串匹配效率。整個過程分為兩步：構(gòu)建next數(shù)組、進行主串與模式串的匹配。

構(gòu)建next數(shù)組（失配函數(shù)）

next數(shù)組記錄模式串每個位置之前的最長相等前后綴長度。這個信息用于在匹配失敗時決定模式串應向右滑動多少位。

具體做法是從左到右遍歷模式串，使用兩個指針 i 和 j，其中 j 表示當前最長前綴的長度：

• 初始化 next[0] = 0，j = 0
• 從 i = 1 開始遍歷模式串
• 如果 pattern[i] == pattern[j]，則 next[i] = ++j，i++
• 否則若 j > 0，則回退 j = next[j - 1]，繼續(xù)比較
• 若 j == 0，則 next[i] = 0，i++

執(zhí)行KMP匹配過程

使用構(gòu)建好的next數(shù)組，在主串中查找模式串出現(xiàn)的位置。同樣使用雙指針技術(shù)：

立即學習“C++免費學習筆記（深入）”；

• 用 i 遍歷主串，j 遍歷模式串
• 如果主串字符與模式串字符相等，i 和 j 同時后移
• 如果不等且 j > 0，則 j 回退到 next[j - 1]
• 如果不等且 j == 0，則僅 i++
• 當 j 達到模式串長度時，說明找到一次匹配，記錄起始位置，并可選擇繼續(xù)搜索

C++代碼實現(xiàn)示例

#include <iostream>
#include <vector>
#include <string>
<p>std::vector<int> buildNext(const std::string& pattern) {
int n = pattern.length();
std::vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
next[i] = j;
}
return next;
}</p><p>std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
std::vector<int> matches;
if (pattern.empty()) return matches;</p><pre class='brush:php;toolbar:false;'>auto next = buildNext(pattern);
int m = text.length();
int n = pattern.length();
int j = 0;

for (int i = 0; i < m; ++i) {
    while (j > 0 && text[i] != pattern[j]) {
        j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
        ++j;
    }
    if (j == n) {
        matches.push_back(i - n + 1);
        j = next[j - 1]; // 準備下一次匹配
    }
}
return matches;

登錄后復制

}

法語寫作助手

法語助手旗下的AI智能寫作平臺，支持語法、拼寫自動糾錯，一鍵改寫、潤色你的法語作文。

31

查看詳情

int main() { std::string text = "ABABDABACDABABCABC"; std::string pattern = "ABABCAB"; auto result = kmpSearch(text, pattern);

for (int pos : result) {
    std::cout << "Pattern found at index " << pos << std::endl;
}

return 0;

登錄后復制

}

上述代碼中，buildNext函數(shù)生成next數(shù)組，kmpSearch函數(shù)返回所有匹配位置。時間復雜度為O(m+n)，空間復雜度O(n)，適合處理長文本中的高效模式匹配。

基本上就這些。掌握next數(shù)組的構(gòu)造邏輯和匹配過程中的狀態(tài)轉(zhuǎn)移，就能靈活應用KMP算法解決實際問題。

以上就是c++++中如何實現(xiàn)KMP算法_c++ KMP算法實現(xiàn)方法的詳細內(nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！