KMP算法通过构建next数组优化字符串匹配，避免主串指针回溯。1. next数组记录模式串各位置最长相等前后缀长度，用于失配时跳转；2. 构建过程用双指针i和j，比较pattern[i]与pattern[j]，相等则更新next[i]=j+1，不等则回退j=next[j-1]；3. 匹配阶段遍历主串，字符相等时双指针进，不等且j>0时j回退，j=0则主串指针进；4. 当j等于模式串长时记录匹配位置并继续搜索。时间复杂度O(m+n)。完整实现包含buildNext与kmpSearch函数，示例中查找"ABABC"在"ABABDABACDABABCABC"中的位置，输出匹配起始下标。核心是利用模式串自身结构减少冗余比较。
在C++中实现KMP（Knuth-Morris-Pratt）字符串匹配算法，核心是通过预处理模式串生成一个部分匹配表（通常称为next数组），避免在匹配失败时回溯主串的指针，从而将时间复杂度优化到O(m + n)。
1. 理解next数组的构建
next数组记录的是模式串每个位置之前的最长相等前后缀长度。这个信息用于在匹配失败时决定模式串应该跳到哪个位置继续比较。
构建next数组的过程如下：
- 初始化next[0] = 0（或-1，取决于实现方式）
- 使用两个指针：i遍历模式串，j表示当前最长前缀的长度
- 如果模式串[i] == 模式串[j]，则next[i+1] = j+1，然后i和j都加1
- 如果不等且j > 0，则回退j = next[j-1]
- 如果j为0，则next[i+1] = 0，i加1
2. 构建next数组代码实现
vector<int> buildNext(const string& pattern) {
int n = pattern.size();
vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
3. KMP主匹配过程
使用构建好的next数组，在主串中查找模式串出现的位置。
立即学习“C++免费学习笔记（深入）”；
- i用于遍历主串，j用于遍历模式串
- 如果字符匹配，i和j都前进
- 如果不匹配且j > 0，则j回退到next[j-1]
- 如果j为0，则只让i前进
- 当j等于模式串长度时，说明找到一次匹配，记录起始位置并继续搜索
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> matches;
if (pattern.empty()) return matches;
<pre class='brush:php;toolbar:false;'>vector<int> next = buildNext(pattern);
int m = text.size(), n = pattern.size();
int j = 0;
for (int i = 0; i < m; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == n) {
matches.push_back(i - n + 1);
j = next[j - 1]; // 继续找下一个匹配
}
}
return matches;}
4. 完整示例调用
#include <iostream>
#include <vector>
#include <string>
using namespace std;
<p>int main() {
string text = "ABABDABACDABABCABC";
string pattern = "ABABC";</p><pre class='brush:php;toolbar:false;'>vector<int> result = kmpSearch(text, pattern);
cout << "Pattern found at positions: ";
for (int pos : result) {
cout << pos << " ";
}
cout << endl;
return 0;}
基本上就这些。KMP的关键在于理解next数组的含义——它保存了模式串自身的结构信息，使得我们可以在失配时跳过不必要的比较。只要把构建next和主匹配两个步骤写清楚，整个算法就很清晰了。
