KMP算法基于有限状态机，根据模式串构建失配函数，在匹配过程中快速恢复，避免重新比较。其优点包括时间复杂度低、高效失配处理、易于实现，缺点是空间复杂度高、需要预处理、对非重复字符敏感。
KMP 算法的依据
KMP 算法（Knuth-Morris-Pratt 算法）的基本依据是有限状态机（FSM）。它根据给定模式串构建一个 FSM，该 FSM 的状态数等于模式串的长度加 1。
通过模式串和文本串的逐个字符比较，FSM 可以高效地识别模式串是否匹配文本串。该算法引入了一个关键概念：失配函数，它表示在 FSM 的某个状态下，如果模式串和文本串不匹配，FSM 应该转移到哪个状态。
优点分析
- 时间复杂度低：KMP 算法的时间复杂度为 O(m + n)，其中 m 是模式串的长度，n 是文本串的长度。与朴素字符串匹配算法的 O(m * n) 相比，这是一个很大的优势。
- 高效的失配处理：失配函数允许 KMP 算法在模式串和文本串不匹配时快速恢复，避免了重新比较模式串的整个前缀。
- 易于实现：KMP 算法的实现相对简单，并且可以轻松地应用于各种编程语言中。
缺点分析
- 空间复杂度高：KMP 算法需要 O(m) 的额外空间来构建失配函数。对于很长的模式串，这可能会成为限制因素。
- 预处理时间：在使用 KMP 算法进行匹配之前，需要预处理模式串以构造失配函数。这个预处理时间可能会影响算法的整体效率，尤其是模式串不断变化时。
- 对非重复字符的敏感性：KMP 算法在模式串中包含大量非重复字符时效率較低。
