描述kmp算法和优化kmp算法的过程

KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的高效算法。它的核心思想是预处理模式串（也称文本），创建一个部分匹配表（Pattern Array，简称PArray），使得当主串中某位置的字符与模式串不匹配时，可以根据PArray快速跳过一些多余的比较，减少不必要的搜索。

KMP过程大致分为以下几个步骤：
1. 构建PArray：对于模式串中的每个前缀，如果它也是后缀，则其最长公共前后缀长度就是下一个位置应该检查的偏移量。
2. 搜索阶段：从主串开始逐位与模式串比较，若相等则继续；如果不等，则查看当前主串字符的位置在PArray中对应的值，决定如何调整主串的位置。
3. 如果当前位置的PArray值是负数，说明之前已经遇到更长的前缀，直接跳过相应次数的字符；如果是0，表示当前位置尚未计算PArray值，向前一位看；否则，移动主串到下一个位置并继续比较。

优化KMP算法主要是针对PArray的构建过程，虽然原始的KMP需要O(n)的时间来构建PArray，但其实可以在线性时间内完成，即只遍历模式串一次就能得到整个PArray。这通常通过“失败函数”（Failure Function，F(i)）的概念实现，F(i)表示前缀到第i个字符为止的最长公共前后缀的长度。