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::vectorbuild_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" 中应匹配三次）。
立即学习“C++免费学习笔记（深入）”；
- 主循环条件是
i ，不是i - 每次成功匹配字符后必须
++i; ++j;，否则会重复比较或卡死 - 当
j == 0 && text[i] != pattern[0]时，只能++i，不能尝试next[-1]
为什么 C++ 中用 std::vector 而不用 int* 手动管理内存
现代 C++ 已无需手动 new/delete。用 std::vector 可避免栈溢出（长模式串导致大数组）、释放遗漏、以及跨函数生命周期问题。尤其当 pattern 是临时对象时，返回 vector 是安全的（C++11 后有移动语义优化）。
如果硬要优化空间（比如嵌入式环境），可将 next 数组复用为局部栈数组，但前提是已知最大模式长度；否则仍推荐 vector ——它的 capacity() 增长策略比手写扩容更可靠，且不会因 realloc 失败而崩溃。
真正容易被忽略的是：KMP 的「线性时间」只在 next 构建和主匹配都完成的前提下成立；如果频繁构造 next（比如每次匹配都重新算），整体就退化为 O(n×m)。实际使用中，应缓存 next 数组，尤其当同一个模式串要匹配多个主串时。
