【杂乱笔记】Kmp字符串匹配算法
KMP 算法逻辑
- 构建
next数组：- 初始化
next数组，用于存储每个位置的最长相同前后缀长度。 - 遍历模式字符串
patt- 如果当前字符与前缀字符匹配，增加前缀长度，并更新
next数组。 - 如果不匹配，使用
next[prefix\_len - 1]回退到上一个可能的前缀长度，继续比较。
- 如果当前字符与前缀字符匹配，增加前缀长度，并更新
- 初始化
- 字符串匹配：
- 初始化两个指针
i和j，分别指向文本text和模式pattern的开头。 - 遍历文本：
- 如果
text[i]和pattern[j]匹配，移动i和j。 - 如果
j达到模式长度，说明匹配成功，记录匹配起始位置。 - 如果不匹配且
j > 0，使用next[j - 1]回退j，继续比较。 - 如果
j == 0，仅移动i。
- 如果
- 初始化两个指针
- 返回结果：
- 如果找到匹配，返回起始索引。
- 如果没有匹配，返回 -1。
Next数组计算中，如果遇到当前字符与前缀字符不匹配的情况，那么就需要重新在前面遍历的内容中寻找次长的最长相同前后缀（对应代码为prefix_len = next[prefix_len - 1];），之后再与当前字符进行匹配（下一次while循环中的if (patt[i] == patt[prefix_len])），如果还是匹配不上，那么就再再去之前的最长相同前后缀再次比较。eg:
某一
patt如下：
Patt A B C A B D Next 0 0 0 1 2 0 在匹配
D时，我们当前的最长前后缀为AB，这时候通过代码prefix_len = next[prefix_len - 1];，我们相当于是去第一个AB中重新匹配，结果发现还是不匹配并且Next数组对应为0，所以D的Next就为0。
#include <iostream>
#include <vector>
#include <string>using namespace std;vector<int> buildNext(const string& patt) {int m = patt.size();vector<int> next(m, 0);int prefix_len = 0;int i = 1;while (i < m) {if (patt[i] == patt[prefix_len]) {prefix_len++;next[i] = prefix_len;i++;} else {if (prefix_len != 0) {prefix_len = next[prefix_len - 1];} else {next[i] = 0;i++;}}}return next;
}int KMPsearch(const string& text, const string& pattern) {vector<int> next = buildNext(pattern);int i = 0; // text 的索引int j = 0; // pattern 的索引int n = text.size();int m = pattern.size();while (i < n) {if (text[i] == pattern[j]) {i++;j++;}if (j == m) {return i - j; // 匹配成功，返回起始索引} else if (i < n && text[i] != pattern[j]) {if (j != 0) {j = next[j - 1];} else {i++;}}}return -1; // 未找到匹配
}int main() {string text = "ababcabcabababd";string pattern = "ababd";int index = KMPsearch(text, pattern);if (index != -1) {cout << "Pattern found at index: " << index << endl;} else {cout << "Pattern not found" << endl;}return 0;
}
补充：前缀函数
此为字符串匹配的另一算法，通过简单转换即可转换为Kmp算法。
pi数组的定义：p[i]表示第i个前缀的最长匹配的真前、后缀的长度。len=pi[len-1];这个解释和上述一样，就是寻找一个类似于回文的字符串。
vecotr<int>pi (str.size(),0);
for(int i=1;i<str.size();i++){int len=pi[i-1];while(len!=0&&str[i]!=str[len]){len=pi[len-1];}if(str[i]==str[len]){p[i]=len+1;}
}