c++ kmp算法代码 c++字符串匹配算法详解

KMP算法通过构建next数组实现高效字符串匹配，避免主串指针回溯，时间复杂度O(n+m)；next数组记录模式串各位置最长相等真前后缀长度，用于失配时确定模式串的滑动位置；例如模式串"ABABC"的next数组为[0,0,1,2,0]；匹配过程中，当字符不匹配且j>0时，j回退到next[j-1]，否则i++；最终输出所有匹配起始位置，如主串"ABABDABACDABABCABC"中找到"ABABC"在位置8匹配。

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串（文本串）中查找一个子串（模式串）的出现位置。与暴力匹配相比，KMP避免了主串指针的回溯，时间复杂度为 O(n + m)，其中 n 是主串长度，m 是模式串长度。

核心思想：利用部分匹配表（Next数组）

KMP 的关键在于预处理模式串，构建一个 next 数组（也叫失败函数或部分匹配表），记录模式串每个位置之前的最长相等真前后缀长度。当匹配失败时，利用 next 数组决定模式串应该跳到哪个位置继续匹配，而不是从头开始。

举个例子：

模式串 "ABABC" 的 next 数组为 [0, 0, 1, 2, 0]。解释如下：

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

• next[0] = 0（单个字符无前后缀）
• next[1] = 0（"AB" 无公共前后缀）
• next[2] = 1（"ABA" 中前缀 "A" 和后缀 "A" 相同）
• next[3] = 2（"ABAB" 中前缀 "AB" 和后缀 "AB" 相同）
• next[4] = 0（"ABABC" 无公共前后缀）

构建 Next 数组（预处理）

使用双指针法构造 next 数组，类似于在模式串自己和自己做匹配：

MD5校验和计算小程序（C）

C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。

下载

void getNext(const string& pattern, vector& next) {
    int m = pattern.length();
    next.resize(m);
    next[0] = 0;
    int len = 0; // 当前最长相等前后缀长度
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1]; // 回退 len
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
}

KMP 匹配过程

主串和模式串进行匹配，当字符不相等时，利用 next 数组移动模式串指针：

#include 
#include 
#include 
using namespace std;

// KMP 主函数，返回所有匹配位置
vector kmpSearch(const string& text, const string& pattern) {
    vector result;
    int n = text.length();
    int m = pattern.length();

    if (m == 0) return result;

    vector next;
    getNext(pattern, next);

    int i = 0; // text 指针
    int j = 0; // pattern 指针

    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == m) {
            result.push_back(i - j); // 找到一次匹配
            j = next[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }

    return result;
}

完整可运行示例

vector matches = kmpSearch(text, pattern);

if (matches.empty()) {
    cout << "未找到匹配" << endl;
} else {
    cout << "模式串在以下位置匹配: ";
    for (int pos : matches) {
        cout << pos << " ";
    }
    cout << endl;
}

return 0;

}

输出结果：
模式串在以下位置匹配: 8

总结与注意事项
KMP 算法的核心优势是主串指针不回退，适合处理大文本搜索。理解 next 数组的含义至关重要 —— 它保存的是“当匹配失败时，模式串应跳转到的位置”。
注意点：

  
next 数组构建时，本质是 pattern 自匹配
  
匹配过程中，j 回退到 next[j-1] 而不是 next[j]
  
若只需找第一个匹配，可在找到后立即返回


基本上就这些，掌握 next 数组的逻辑是理解 KMP 的关键。