企业官网建设流程全解析

前言

字符串匹配要解决的问题是：在文本串 T 中找出模式串 P 出现的所有位置。朴素算法把 P 的开头对齐到 T 的每个位置，逐字符比较，一旦失配就把 P 整体右移一位、从 P 的第一个字符重新开始。最坏情况下，例如 T 是「aaaa...a」、P 是「aaaab」，每一轮都要比较 |P| 次才失配，总复杂度是 O(|T|×|P|)。

KMP 算法（Knuth–Morris–Pratt）的核心观察是：失配时，已经比较过的那一段文本包含了信息，不需要把模式串退回开头。利用模式串自身的「前缀等于后缀」结构，可以把 P 一次右移多位，并且文本指针永不回退，总复杂度降到 O(|T|+|P|)。

初学者常见的误解有三个。第一，以为 KMP 的next数组只有一种定义——不同教材有「前缀函数」「失配后跳转位置」「整体右移一位」等版本，数值差一，混用会得到错误结果。第二，以为 KMP 在任何输入上都比朴素算法快——对于随机文本，朴素算法平均表现并不差，KMP 的优势体现在最坏情况和大量重复字符的输入。第三，忘了处理空模式串和重叠匹配。本文统一采用前缀函数（prefix function）定义，给出 C++17 实现并逐行说明。

一、前缀函数的定义

对模式串 P（长度 m），前缀函数pi[i]定义为：子串P[0..i]的最长真前缀，它同时又是该子串的真后缀，这个前缀的长度就是pi[i]的值。真前缀指不包括整个子串本身的前缀。

以 P =ababc为例：

得到pi = [0, 0, 1, 2, 0]。

这个数组的含义是：如果在P[j]处失配，说明P[0..j-1]已经和文本的某一段匹配上了；这段文本的后缀等于P[0..j-1]的某个前缀，长度正是pi[j-1]。于是可以把 P 右移，让P[pi[j-1]]对准当前位置继续比较，而不必回退文本指针。

二、线性构造前缀函数

朴素地求每个pi[i]需要枚举所有前后缀，最坏是 O(m³)。KMP 的构造利用前一个结果递推：

// 适用于 C++17
#include <cstddef>
#include <string>
#include <vector>

std::vector<std::size_t> build_prefix(const std::string& pattern) {
std::vector<std::size_t> pi(pattern.size(), 0);
for (std::size_t i = 1; i < pattern.size(); ++i) {
std::size_t k = pi[i - 1]; // 候选长度
while (k > 0 && pattern[i] != pattern[k]) {
k = pi[k - 1]; // 退到次长的相等前后缀
}
if (pattern[i] == pattern[k]) {
++k;
}
pi[i] = k;
}
return pi;
}

逐点解释：

• 
  
• k表示当前已知的、P[0..i-1]的最长相等前后缀长度，同时也是下一个待比较字符的下标。
• 
  
• 如果P[i] == P[k]，相等前后缀可以延长一位，pi[i] = k + 1。
• 
  
• 如果不等，就沿着pi[k-1]回退，寻找一个更短但仍相等的前后缀。回退可能连续发生，所以用while。
• 
  
• k只会增加或减少，且每次减少都对应之前某次增加，总的回退次数不超过总增加次数，因此整个循环是 O(m) 的均摊复杂度。
• 
  

注意pattern[i] == pattern[k]这一行：当k == 0且字符不相等时，它仍然会执行一次比较，结果为假，pi[i]保持 0，这是正确的。当pattern为空时，循环不进入，返回空数组，不会越界。

三、匹配过程

匹配阶段维护两个指针：i扫描文本，j表示当前已匹配的模式串长度。文本指针只前进不后退。下面的函数复用上文的build_prefix，实际使用时两者应放在同一个源文件中：

// 适用于 C++17
#include <cstddef>
#include <string>
#include <vector>

std::vector<std::size_t> kmp_search(const std::string& text,
const std::string& pattern) {
std::vector<std::size_t> positions;
if (pattern.empty()) {
return positions; // 约定：空模式串不产生匹配
}

const std::vector<std::size_t> pi = build_prefix(pattern);
std::size_t j = 0;

for (std::size_t i = 0; i < text.size(); ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = pi[j - 1]; // 失配，按前缀函数回退
}
if (text[i] == pattern[j]) {
++j; // 当前字符匹配成功
}
if (j == pattern.size()) {
positions.push_back(i + 1 - pattern.size());
j = pi[j - 1]; // 继续寻找重叠匹配
}
}
return positions;
}

这里有两个边界需要确认。第一，进入循环时j一定小于pattern.size()：初始为 0；每次命中后立刻被重置为pi[m-1]，而pi的值最大是m-1，所以pattern[j]不会越界。第二，最后一行用pi[j-1]而不是把j置 0，是为了支持重叠匹配。例如在aaaa中找aa，正确答案是位置 0、1、2；若命中后置 0，就会漏掉后两个。

以 T =abababc、P =ababc为例，手工推演如下：

按标准语义，结果应当是{2}，即ababc从下标 2 开始。

四、复杂度、变体与替代方案

KMP 的总复杂度是 O(n+m)，空间 O(m)。它适合模式串固定、文本很长甚至以流的形式到达的场景，因为文本只需扫描一遍。

教材里另一个常见版本叫next数组，通常定义为「失配时模式串应跳到的位置」，数值与前缀函数相差 1，有的实现还会把next[0]设为 -1。两种写法本身都对，但不能把一份代码里的数组直接套到另一份代码的循环里。阅读他人代码时，先确认它维护的是「已匹配长度」还是「下一个比较位置」。

C++17 的标准库也提供了内置的搜索器。std::search的默认实现最坏复杂度是 O(n×m)，但可以传入 Boyer–Moore 搜索器：

// 适用于 C++17
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>

int main() {
const std::string text = "abababc";
const std::string pattern = "ababc";

auto searcher = std::boyer_moore_searcher(pattern.begin(), pattern.end());
auto it = std::search(text.begin(), text.end(), searcher);
if (it != text.end()) {
std::cout << "found at " << (it - text.begin()) << '\n';
}
return 0;
}

Boyer–Moore 系列在实践中往往很快，但它需要额外的表和哈希支持，最坏情况下并不保证线性时间。选择时看需求：教学、面试和需要严格线性保证时写 KMP；工程里模式固定且追求通用性时，可以直接用标准库搜索器，具体行为以所用标准库实现和官方文档为准。

前缀函数还有一个常用推论：长度为 m 的字符串的最小周期是m - pi[m-1]，当且仅当m % (m - pi[m-1]) == 0时该周期能整除整个长度。这个性质常用于判断题和字符串周期问题。

常见坑点

❌ 把next数组与前缀函数混用，失配时写j = next[j]，导致死循环或漏匹配。 ✅ 统一约定：本文的pi[i]是长度，失配回退用j = pi[j-1]；换实现时先确认下标语义。

❌ 匹配成功后把j置 0，漏掉重叠出现的位置。 ✅ 置j = pi[j-1]，保留可能的后缀重叠；只有明确要求不重叠时才置 0。

❌ 构造前缀函数时用if而不是while回退。 ✅ 失配可能连续回退多层，必须用while (k > 0 && ...)。

❌ 忘记处理空模式串，访问pi[-1]或pattern[0]。 ✅ 单独判断pattern.empty()，按接口约定返回空结果或抛异常。

❌ 认为 KMP 一定比std::string::find快。 ✅ 标准库实现可能使用更快的算法；KMP 的价值在于最坏情况的线性保证，实际性能应测量。

❌ 用int存std::string::size_type级别的位置，超长文本溢出。 ✅ 位置和长度用std::size_t，比较时避免有符号/无符号混用。

❌ 在文本流式到达时试图回退文本指针。 ✅ KMP 的设计正是文本指针单向前进；保持这一点才能流式处理。

❌ 把前缀函数当成「最长公共前后缀」后直接用于任意子串查询。 ✅pi只描述从下标 0 开始的前缀；任意区间需要额外结构（如 Z 函数、后缀自动机）。

总结

KMP 的难点不在代码长度，而在下标语义。只要牢牢记住「pi[i]是长度、失配回退到pi[j-1]、命中后也回退到pi[j-1]」，构造和匹配两段代码就是同一个模式。理解前缀函数的递推过程，比背下模板更有价值，因为所有变体都只是在这一个定义上做偏移。