問題關鍵：完成首次匹配之后需要繼續進行模式匹配。

?到這一步后，我們不能直接將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;
}    

輸出結果：