理论与进阶专题
字符串匹配
字符串匹配要解决的是：在一段较长的文本里，找出一个较短的模式串出现在何处——这正是你按下 Ctrl-F 在文档里查找时发生的事。我们把文本长度记为 n，模式串长度记为 m。最老实、最直白的办法是朴素算法：把模式对齐到文本的第一个位置，逐字符比较；若匹配则报告，若不匹配就把模式向右滑一格再试。简单而正确。
麻烦在它的最坏情形。大约 n 个起始位置中，每一个都可能在出现不匹配前比较多达 m 次，因此朴素法的代价是 O(nm)——而像在一长串「aaaaaaaa…」中查找「aaaab」这类刁钻输入，确实会触到这个上界。浪费之处在于：一次部分匹配失败后，朴素法把刚学到的一切统统丢弃，让模式从头重来，把已经看过的文本字符又看一遍。
Knuth-Morris-Pratt 算法（KMP）正好修掉这份浪费，达到 O(n + m)。它的关键洞见是：当不匹配发生在模式中途时，已经匹配上的那些字符本就是模式自身的一部分，因此我们往往已经知道模式的某个前缀仍然对得上——根本不必重新检查它。KMP 预先算出一张小小的「前缀表」（又称失配函数），对模式中的每个位置，记录在此结束的、既是前缀又是后缀的最长长度。建表代价 O(m)；随后文本只被扫一遍、绝不回退，代价 O(n)。它的思路是「记住，而非重扫」——这就把一次乘法变成了一次加法。
// naive O(n*m): re-checks text it has already seen
std::vector<int> findAll(const std::string& text,
const std::string& pat) {
std::vector<int> hits;
int n = text.size(), m = pat.size();
for (int i = 0; i + m <= n; ++i) { // each start position
int j = 0;
while (j < m && text[i + j] == pat[j]) ++j; // up to m compares
if (j == m) hits.push_back(i); // full match at i
}
return hits; // KMP avoids the restarts
}朴素匹配是 O(nm)；KMP 的前缀表把它降到 O(n + m)。
KMP 的前缀表（失配函数）就是全部诀窍：它告诉搜索在不匹配后能安全地把模式跳多远，从而绝不重扫文本。
又称
另见