1. 是什么
KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，由Donald Knuth、Vaughan
Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少
字符串匹配过程中的回溯次数，从而提高匹配效率。
2. 核心功能
KMP算法的核心功能包括：
预处理：首先，根据给定的模式串计算出部分匹配表。
匹配：在主串中查找模式串，利用部分匹配表减少不必要的字符比较，提高匹配效率。
3. 使用方法
使用KMP算法进行字符串匹配的步骤如下：
4. 创建部分匹配表：根据给定的模式串，计算出部分匹配表。
5. 匹配过程：
从主串的起始位置开始，将模式串的第一个字符与主串的字符进行比较。
如果字符匹配，则继续比较后续字符。
如果字符不匹配，则使用部分匹配表确定模式串的下一个起始位置，并继续匹配过程。
重复上述步骤，直到找到模式串在主串中的位置，或者模式串遍历完毕。
6. 实际应用场景
KMP算法在许多实际应用场景中都非常有用，以下是一些例子：
文本编辑器：在文本编辑器中，可以使用KMP算法来查找和替换文本。
数据压缩：在数据压缩算法中，可以使用KMP算法来查找重复的字符串，并对其进行压缩。
文本处理：在文本处理应用程序中，可以使用KMP算法来查找关键词、短语或模式。
字符串匹配：在字符串匹配问题中，可以使用KMP算法来查找一个字符串在另一个字符串中的位置。
5. 案例
以下是一个使用KMP算法进行字符串匹配的简单案例：
假设我们有一个主串 s = "abcabcabc" 和一个模式串 p = "abc"，我们需要在主串中查找模式串。
6. 首先，计算部分匹配表：
对于模式串 p = "abc"，部分匹配表为 [0, 0, 0]。
7. 匹配过程：
从主串的起始位置开始，将模式串的第一个字符与主串的字符进行比较。
字符 'a' 匹配，继续比较字符 'b' 和 'b'。
字符 'c' 不匹配，根据部分匹配表，模式串的下一个起始位置为 0。
将模式串的第一个字符与主串的下一个字符进行比较。
字符 'a' 匹配，继续比较字符 'b' 和 'b'。
字符 'c' 不匹配，根据部分匹配表，模式串的下一个起始位置为 0。
