c++中如何实现字符串的kmp算法_c++ KMP模式匹配详解_技术教程

next数组表示模式串各前缀的最长真公共前后缀长度，用于KMP算法中实现主串指针不回退；因std::string::find不暴露中间状态且底层不保证KMP，故需手写build_next函数，注意next[0]=0、双指针正确更新及边界处理。

什么是 `next` 数组，为什么不能直接用 `std::string::find`

因为 std::string::find 底层不保证是 KMP，且无法获取匹配过程中的中间状态（比如每次失配跳转位置），而 KMP 的核心价值恰恰在于 next 数组驱动的「不回退主串指针」行为。它适用于流式处理、自定义匹配逻辑或教学分析场景。

next[i] 表示模式串 pattern[0..i] 的最长真前缀同时也是后缀的长度。注意：不同教材对 next 定义略有差异——有的存的是「最大公共前后缀长度减 1」，有的存「下一次应比较的位置索引」。C++ 实现中建议统一用「长度版」，避免负索引和边界混淆。

若 pattern = "ababaca"，则 next = [0,0,0,1,2,3,0]
构建时用双指针：j 指向当前待求位置，i 指向前缀末尾；当 pattern[i] == pattern[j] 时，next[j++] = i + 1
失配时，i 不回退主串位置，而是根据 next[i-1] 跳转模式串位置

如何手写 `build_next` 函数避免越界和逻辑错位

常见错误是把 next[0] 设为 -1 或未初始化，导致后续 i 变成负数；或者在构建循环里误用 i 导致死循环。正确做法是让 next[0] = 0，并用 i = 0 作为前缀长度计数器。

std::vector build_next(const std::string& pattern) {
    if (pattern.empty()) return {};
    std::vector next(pattern.size(), 0);
    int i = 0; // 当前匹配的前缀长度
    for (int j = 1; j < pattern.size(); ++j) {
        while (i > 0 && pattern[i] != pattern[j]) {
            i = next[i - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++i;
        }
        next[j] = i;
    }
    return next;
}

KMP 主匹配循环里怎么控制 `i` 和 `j` 不越界

主串索引 i 必须严格递增（这是 KMP 高效的关键），模式串索引 j 在失配时靠 next 回跳。最容易漏掉的判断是：当 j == pattern.size() 时，说明完成一次匹配，此时要先记录位置，再令 j = next[j - 1] 继续找重叠匹配（如 pattern="aa" 在 "aaaa" 中应匹配三次）。