KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。它的主要优势在于在匹配过程中避免了不必要的回溯，提高了匹配效率。

KMP算法的核心思想是利用已经匹配过的信息，避免在模式串与文本串匹配过程中进行不必要的回溯。它通过构建一个部分匹配表（也称为失配函数），记录模式串中每个位置的最长可匹配前缀和后缀的长度，从而在匹配过程中通过查表来决定下一次匹配的位置。相关原理建议看文后的参考链接，讲得非常细致，可以先看3，再看1和2。

下面是KMP算法的代码实现（使用C++语言），下面是用KMP算法找寻text串中第一个pattern串的索引位置的代码：

#include <iostream>
#include <vector>using namespace std;vector<int> buildPartialMatchTable(const string& pattern) {int m = pattern.length();vector<int> next(m, 0);int i = 1, j = 0;while (i < m) {if (pattern[i] == pattern[j]) {j++;next[i] = j;i++;} else {if (j != 0) {j = next[j - 1];} else {next[i] = 0;i++;}}}return next;
}int kmpSearch(const string& text, const string& pattern) {int n = text.length();int m = pattern.length();if (m == 0) {return 0;}if (n == 0) {return -1;}vector<int> next = buildPartialMatchTable(pattern);int i = 0, j = 0;while (i < n) {if (text[i] == pattern[j]) {i++;j++;if (j == m) {return i - j;}} else {if (j != 0) {j = next[j - 1];} else {i++;}}}return -1;
}int main() {string text = "sadbutsad";string pattern = "sad";int index = kmpSearch(text, pattern);if (index != -1) {cout << "Pattern found at index " << index << endl;} else {cout << "Pattern not found" << endl;}return 0;
}

上面是用while循环写的逻辑，可以使用for循环更简洁点：

#include <iostream>
#include <vector>using namespace std;vector<int> buildPartialMatchTable(const string& pattern) {int m = pattern.length();vector<int> next(m, 0);int i = 1, j = 0;for (int i = 1; i < m; ++i){while (j > 0 && pattern[i] != pattern[j])j = next[j - 1];if (pattern[i] == pattern[j])++j;next[i] = j;}return next;
}int kmpSearch(const string& text, const string& pattern) {int n = text.length();int m = pattern.length();if (m == 0) {return 0;}if (n == 0) {return -1;}vector<int> next = buildPartialMatchTable(pattern);int i = 0, j = 0;for (int i = 0; i < n; ++i){while (i > 0 && text[i] != pattern[j])j = next[j - 1];if (text[i] == pattern[j])++j;if (j == m)return i - m + 1;}return -1;
}int main() {string text = "sadbutsad";string pattern = "sad";int index = kmpSearch(text, pattern);if (index != -1) {cout << "Pattern found at index " << index << endl;} else {cout << "Pattern not found" << endl;}return 0;
}

输出：

KMP算法力扣相关的题目：

28. 找出字符串中第一个匹配项的下标

相关参考：

1. 代码随想录-28. 实现 strStr()
2. 【宫水三叶】简单题学 KMP 算法
3. 灵茶山艾府的知乎回答：如何更好地理解和掌握 KMP 算法?