C++怎么实现一个KMP字符串匹配算法_C++算法设计与KMP原理-C++-PHP中文网

C++怎么实现一个KMP字符串匹配算法_C++算法设计与KMP原理

下次还敢

发布： 2025-11-25 15:18:08

原创

908人浏览过

KMP算法通过构建next数组实现高效字符串匹配，利用模式串自身重复信息减少主串指针回退，在O(n+m)时间内完成匹配。核心是预处理生成部分匹配表（next数组），记录各位置最长相等前后缀长度；匹配时失配则根据next数组移动模式串指针，避免主串指针回溯。C++实现包含buildNext和kmpSearch函数，分别构造next数组并执行搜索，适用于长文本场景，较暴力匹配更稳定高效。

c++怎么实现一个kmp字符串匹配算法_c++算法设计与kmp原理

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能够在O(n + m)时间内找出模式串在主串中的位置，避免了暴力匹配中大量的回溯。C++实现KMP的关键在于预处理模式串生成“部分匹配表”（即next数组），然后利用该表跳过不必要的比较。

理解KMP的核心思想

KMP算法的核心是利用模式串自身的重复信息来减少主串指针的回退。当匹配失败时，主串指针不回退，仅移动模式串指针到合适位置，这个位置由next数组决定。

next数组记录的是：对于模式串每个位置j，其前面子串的最长相等前缀与后缀的长度。例如模式串"ABABC"，在位置4（字符'C'前），最长公共前后缀是"AB"，长度为2，因此next[4] = 2。

构建next数组（失配函数）

next数组的构造过程也是一个类似KMP匹配的过程，本质上是模式串自己和自己匹配。

立即学习“C++免费学习笔记（深入）”；

初始化next[0] = 0，因为单个字符没有真前后缀
使用两个指针i和j，i遍历模式串，j表示当前最长公共前后缀长度
若pattern[i] == pattern[j]，则next[i+1] = j+1，i和j同时后移
若不相等且j > 0，则j回退到next[j-1]继续比较
若j=0，则next[i+1]=0，i继续后移

代码实现：

<font face="Courier New,Courier,monospace">vector<int> buildNext(const string& pattern) {
    int m = pattern.length();
    vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}</font>

登录后复制

执行KMP字符串匹配

使用构建好的next数组进行主串和模式串的匹配。

小鸽子助手

一款集成于WPS/Word的智能写作插件

查看详情

用i遍历主串，j遍历模式串
字符相等时，i和j都加1
不相等时，若j > 0，则j回退到next[j-1]；否则i加1
当j等于模式串长度时，说明找到一次匹配，记录位置并继续

完整匹配函数：

<font face="Courier New,Courier,monospace">vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> positions;
    if (pattern.empty()) return positions;
<pre class='brush:php;toolbar:false;'>vector<int> next = buildNext(pattern);
int n = text.length();
int m = pattern.length();
int j = 0;

for (int i = 0; i < n; i++) {
    while (j > 0 && text[i] != pattern[j]) {
        j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
        j++;
    }
    if (j == m) {
        positions.push_back(i - m + 1);
        j = next[j - 1]; // 继续查找下一个匹配
    }
}
return positions;

登录后复制

}

使用示例与注意事项

调用方式简单：

<font face="Courier New,Courier,monospace">int main() {
    string text = "ABABDABACDABABCABC";
    string pattern = "ABABC";
    vector<int> result = kmpSearch(text, pattern);
    for (int pos : result) {
        cout << "Match found at index " << pos << endl;
    }
    return 0;
}</font>

登录后复制

注意边界情况：空模式串、完全匹配、无匹配等。next数组构造是关键，理解j的回退逻辑是掌握KMP的重点。

基本上就这些。KMP虽然初看复杂，但只要搞懂next数组的意义和构造过程，实现起来并不难。在实际应用中，它比暴力匹配稳定高效，尤其适合长文本搜索场景。

以上就是C++怎么实现一个KMP字符串匹配算法_C++算法设计与KMP原理的详细内容，更多请关注php中文网其它相关文章！