KMP算法的详细解释

KMP算法全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的经典算法。它的目的是在一个主串中查找是否存在给定的模式串。相比于简单的线性搜索，如Brute Force搜索，KMP算法更高效，尤其是在模式串重复或者频繁出现的情况下。

KMP算法的核心思想是利用已经匹配过的部分信息，通过一个叫做“失配指针”的数组（也叫作部分匹配表或失配函数）来跳过多余的比较。算法步骤如下：

1. **构建失配函数**：对于模式串的每个位置i，计算到前缀子串的最长公共前后缀长度，记为lps[i]。如果当前字符和下一个字符相等，lps[i+1] = lps[i] + 1；否则，寻找lps[i]处的前缀子串与剩余部分的最大公共前后缀，即lps[i+1] = lps[i]。

2. **搜索过程**：在主串中从头开始逐个字符匹配模式串。遇到不匹配时，先检查失配指针，若它大于0，说明之前的某次成功匹配的位置发生了错误，因此向前移动失配指针继续尝试；否则，直接移动主串指针继续匹配。

3. **找到匹配或失败**：当模式串匹配成功时返回匹配起始位置；如果模式串结束后还没有找到匹配，则返回-1表示未找到。