KMP（Knuth-Morris-Pratt）算法是一种用于在文本字符串（通常称为“文本”）中搜索一个词（通常称为“模式”或“子串”）的高效算法。KMP算法通过避免不必要的字符比较来提高搜索效率。其核心思想是利用已经部分匹配这个信息，避免从头开始比较。
基本概念
前缀：一个字符串的前缀是指字符串从第一个字符开始到某个字符之前的所有字符组成的子串。
后缀：一个字符串的后缀是指字符串从某个字符开始到最后一个字符之前的所有字符组成的子串。
最长公共前后缀：一个字符串的最长公共前后缀是指既是该字符串的前缀也是后缀的最长子串。
KMP算法步骤
预处理模式串：计算模式串的“部分匹配表”（也称为“失败函数”或“跳转表”）。这个表记录了当模式串中的某个字符与文本串中的字符不匹配时，模式串应该向右移动多少位。
匹配过程：
初始化两个指针，一个指向文本串的起始位置（记作i），另一个指向模式串的起始位置（记作j）。
当i小于文本串长度且j小于模式串长度时，执行以下操作：
如果当前字符匹配（即text[i] == pattern[j]），则i和j都向右移动一位。
如果当前字符不匹配，则根据部分匹配表将j移动到正确的位置，i保持不变。
如果j已经到达模式串的末尾，说明找到了一个匹配项，返回i - j + 1（即匹配项在文本串中的起始位置）。
如果i已经到达文本串的末尾，说明没有找到匹配项，返回-1。
部分匹配表（跳转表）的计算
部分匹配表是通过分析模式串本身