c++怎么实现一个高效的字符串匹配算法(KMP)_c++ KMP算法实现与原理讲解

KMP算法通过构建next数组避免主串指针回退，在O(n+m)时间内完成字符串匹配，核心是利用模式串的最长相等前后缀信息进行跳转，实现高效搜索。

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能在 O(n + m) 时间内找出模式串在主串中的位置，避免了暴力匹配中不必要的回溯。下面详细讲解其原理并给出 C++ 实现。

核心思想：利用已匹配部分的信息

在暴力匹配中，一旦失配，主串指针会回退，导致重复比较。KMP 的关键是 不回退主串指针，而是根据模式串的结构，移动模式串，跳过不可能匹配的位置。

实现这一点的核心是构建一个叫做 next 数组（也叫失效函数或部分匹配表），记录模式串每个位置前最长的相等前缀和后缀长度。

next 数组的构造

next[i] 表示模式串从 0 到 i 这一段中，最长的相等真前缀与真后缀的长度。

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

例如模式串 "ABABC"：

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

• "A" → 0
• "AB" → 0
• "ABA" → 1 ("A")
• "ABAB" → 2 ("AB")
• "ABABC" → 0

构造过程类似 KMP 匹配，用两个指针 j 和 i，j 表示当前最长前缀的下一个位置，i 遍历模式串。

// 构建 next 数组 vector buildNext(const string& pat) { int m = pat.length(); vector next(m, 0); int j = 0; // 最长相等前后缀的长度 for (int i = 1; i < m; ++i) { while (j > 0 && pat[i] != pat[j]) { j = next[j - 1]; } if (pat[i] == pat[j]) { j++; } next[i] = j; } return next; }

KMP 主匹配过程

使用 next 数组，在主串中逐个比较字符。当发生失配时，模式串指针回退到 next[j-1] 的位置，而不是从头开始。

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) {
        return i - m + 1; // 找到匹配，返回起始下标
    }
}
return -1; // 未找到

完整可运行示例

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) {
        return i - m + 1;
    }
}
return -1;

基本上就这些。理解 next 数组的含义和构造方式是掌握 KMP 的关键。代码不复杂但容易忽略细节，比如 while 循环中的回退逻辑。多调试几个例子有助于加深理解。

以上就是c++++怎么实现一个高效的字符串匹配算法(KMP)_c++ KMP算法实现与原理讲解的详细内容，更多请关注php中文网其它相关文章！