KMP算法是一种高效的字符串匹配算法,全称为Knuth-Morris-Pratt算法。该算法由D.E.Knuth,J.H.Morris
和V.R.Pratt提出,其核心思想是通过预处理模式串(也称子串)的部分匹配信息,在匹配失败时尽可能地移
动模式串的指针,以减少匹配次数,从而达到快速匹配的目的。
具体实现上,KMP算法使用一个next()函数,该函数包含模式串的局部匹配信息。在匹配失败时,next()函数
用来确定模式串的最左可能有效匹配位置,而非简单地将模式串重新从左向右扫描。这样大大减少了不必要
的匹配次数,提高了算法的效率。
KMP算法的时间复杂度为O(n+m),其中n和m分别为主串和模式串的长度。这是因为最坏情况下,字符串匹
配问题需要比较n个主串字符和m个模式串字符,即需要执行n+m次比较操作。
KMP算法的应用场景包括但不限于在字符串(也称主串)中查找子串的出现位置、计算子串在主串中出现的
次数等。
以下是使用C++实现KMP算法的示例代码:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算next数组
void getNext(string pattern, vector<int>& next) {
int m = pattern.length();
next[0] = 0; // 初始位置
for (int i = 1; i < m; i++) {
int j = next[i - 1]; // 当前位置的前一个匹配位置
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1]; // 向前回溯,直到找到相同字符或回溯到0
}
if (pattern[i] == pattern[j]) {
j++; // 更新匹配位置
}
next[i] = j; // 更新next数组
}
}
// KMP算法匹配字符串
vector<int> kmp(string text, string pattern) {
int n = text.length();
int m = pattern.length();
vector<int> result; // 存储匹配位置的数组
if (m == 0) {
return result; // 空模式串,返回空数组
}
vector<int> next(m); // 存储部分匹配信息的数组
getNext(pattern, next); // 计算next数组