【杂乱笔记】Kmp字符串匹配算法

KMP 算法逻辑

1. 构建 next 数组：
   • 初始化 next 数组，用于存储每个位置的最长相同前后缀长度。
   • 遍历模式字符串patt
     • 如果当前字符与前缀字符匹配，增加前缀长度，并更新 next 数组。
     • 如果不匹配，使用 next[prefix\_len - 1] 回退到上一个可能的前缀长度，继续比较。
2. 字符串匹配：
   • 初始化两个指针 i 和 j，分别指向文本 text 和模式 pattern 的开头。
   • 遍历文本：
     • 如果 text[i] 和 pattern[j] 匹配，移动 i 和 j。
     • 如果 j 达到模式长度，说明匹配成功，记录匹配起始位置。
     • 如果不匹配且 j > 0，使用 next[j - 1] 回退 j，继续比较。
     • 如果 j == 0，仅移动 i。
3. 返回结果：
   • 如果找到匹配，返回起始索引。
   • 如果没有匹配，返回 -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;}
}