KMP模式匹配算法是什么

KMP模式匹配算法，全称为Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法。它主要用于在一个文本字符串S内查找一个词W的出现位置。这个算法的核心是利用已经部分匹配的有效信息，保持词的前缀向右滑动的位数，不需要像暴力匹配那样每次从主字符串的一个字符开始重新比较。

KMP算法的关键在于计算一个部分匹配表（也称为失败函数或者next数组），这个表能够记录模式串在遇到不匹配情况时，模式串应该向右滑动的最优距离，这样可以避免重复比较已经匹配过的字符。具体来说，部分匹配表的每一个值表示在模式串的某个子串中，最长相等的前缀后缀的长度。

KMP算法的大致步骤如下：
1. 构造部分匹配表（next数组）。
2. 在文本字符串S中使用模式串W和next数组进行匹配：
- 如果当前位置字符匹配，则继续向后比较下一个字符。
- 如果不匹配，根据next数组找到模式串中下一个应该匹配的位置，而不需要每次都从文本串的下一个字符开始。
3. 重复以上步骤，直到模式串完全匹配或者文本串遍历完毕。

KMP算法的优点是可以在O(n+m)的时间复杂度内完成匹配（其中n是文本字符串的长度，m是模式串的长度），而普通的暴力匹配算法的时间复杂度为O(n*m)。