利用KMP找出模式串在目标串中所有匹配位置的起始下标

问题关键：完成首次匹配之后需要继续进行模式匹配。

 到这一步后，我们不能直接将j = 0然后开始下一轮匹配，因为已经匹配过的部分（蓝色部分）中仍然可能存在与模式串重叠的子串：
 

解决办法：

找到蓝色部分的最大相同前后缀，利用next数组，将 j 回溯到最大前缀的后一个位置开始与目标串进行第二轮匹配。

常见的next数组有两种：

1、当前字符对应的next值是不包括本身的最大相同前后缀字符数：

2、当前字符对应的next值是包括本身的最大相同前后缀字符数：

对于第二种情况，只需在第一轮匹配完成后，如果 i 没有到达目标串末尾，让 j = next[j - 1]即可。

对于第一种情况，则需要将next扩容一位，即next数组最后一位的值是整个模式串中最大相同前后缀的字符数，然后在第一轮匹配完成后，如果 i 没有到达目标串末尾，让 j = next[ j ]即可。
 

参考代码：
next数组是第二种情况
 

#include <iostream>
#include <vector>
#include <string>// 构建 next 数组
void computeNext(const std::string& pattern, std::vector<int>& next) {int m = pattern.length();int len = 0;int i = 1;next[0] = 0;while (i < m) {if (pattern[i] == pattern[len]) {len++;next[i] = len;i++;} else {if (len != 0) {len = next[len - 1];} else {next[i] = 0;i++;}}}
}// KMP 算法
std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();std::vector<int> next(m);std::vector<int> result;computeNext(pattern, next);int i = 0; // 文本串的索引int j = 0; // 模式串的索引while (i < n) {if (pattern[j] == text[i]) {j++;i++;}if (j == m) {result.push_back(i - j);j = next[j - 1];} else if (i < n && pattern[j] != text[i]) {if (j != 0) {j = next[j - 1];} else {i++;}}}return result;
}int main() {std::string text = "aaaaaaa";std::string pattern = "aaa";std::vector<int> positions = kmpSearch(text, pattern);if (positions.empty()) {std::cout << "未找到匹配的子串。" << std::endl;} else {std::cout << "匹配的起始下标为: ";for (int pos : positions) {std::cout << pos << " ";}std::cout << std::endl;}return 0;
}    

输出结果：