KMP算法的核心思想是当字符串匹配出现失配时，不需要回退主串的指针，而是利用已经匹配的部分信息，让模式串尽可能移动到正确的位置继续匹配，从而减少不必要的比较次数，整体时间复杂度可以稳定在O(n+m)，其中n是主串长度，m是模式串长度。
KMP算法核心原理
KMP算法最关键的部分是next数组，也叫部分匹配表。这个数组记录了模式串中每个位置之前的前缀和后缀的最长公共长度。当匹配失败时，模式串根据next数组的值跳转，而不是重新从头开始匹配。
举个例子，模式串为ababaca，它的next数组推导逻辑如下：
- 位置0：没有前后缀，长度为0
- 位置1：前缀
a，后缀b，无公共部分，长度为0 - 位置2：前缀
a,ab，后缀b,ab，公共部分ab长度为2 - 以此类推，最终得到对应位置的公共长度
next数组的C++实现
计算next数组的过程其实也是模式串的自我匹配过程，我们用两个指针，一个指向当前计算的位置，一个指向当前最长公共前缀的末尾，逐步递推每个位置的next值。
#include <vector>
#include <string>
using namespace std;
// 计算模式串的next数组
vector<int> getNext(const string& pattern) {
int m = pattern.size();
vector<int> next(m, 0);
// next[0]固定为0，因为第一个字符没有前后缀
int j = 0;
// i从1开始遍历模式串的每个位置
for (int i = 1; i < m; i++) {
// 当j>0且当前字符不匹配时，回退j到next[j-1]
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
// 如果字符匹配，j自增
if (pattern[i] == pattern[j]) {
j++;
}
// 记录当前位置的next值
next[i] = j;
}
return next;
}
完整KMP匹配函数实现
得到next数组之后，就可以实现主串和模式串的匹配逻辑了，匹配过程中主串指针不需要回退，只调整模式串的指针即可。
// KMP字符串匹配函数，返回模式串在主串中第一次出现的位置，没找到返回-1
int kmpSearch(const string& text, const string& pattern) {
if (pattern.empty()) return 0;
vector<int> next = getNext(pattern);
int j = 0; // 模式串的指针
// 遍历主串
for (int i = 0; i < text.size(); i++) {
// 失配时回退模式串指针
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
// 字符匹配，模式串指针后移
if (text[i] == pattern[j]) {
j++;
}
// 模式串全部匹配完成，返回起始位置
if (j == pattern.size()) {
return i - j + 1;
}
}
// 遍历完主串没找到匹配
return -1;
}
测试示例
我们写一个简单的测试代码验证KMP算法的正确性：
#include <iostream>
int main() {
string text = "abababacaba";
string pattern = "ababaca";
int pos = kmpSearch(text, pattern);
if (pos != -1) {
cout << "模式串在主串中的起始位置为：" << pos << endl;
} else {
cout << "主串中未找到模式串" << endl;
}
return 0;
}
运行上述代码，会输出模式串在主串中的起始位置为2，符合预期匹配结果。
算法复杂度与适用场景
KMP算法的时间复杂度是O(n+m)，空间复杂度是O(m)，适合处理主串和模式串都比较长的匹配场景，尤其是需要多次匹配同一个模式串的情况，提前计算好next数组后，每次匹配的效率都很高。
需要注意的是，如果模式串很短，或者匹配场景很少，暴力匹配的实现更简单，开销也更小，不需要盲目使用KMP算法。开发者可以根据实际的业务场景选择合适的字符串匹配方案。