前缀函数与KMP模式匹配算法详解

"AS.md" 本文档主要介绍了前缀函数（Prefix Function）以及基于前缀函数的KMP（Knuth-Morris-Pratt）模式匹配算法。前缀函数是解决字符串匹配问题的重要工具，用于找到一个字符串中最长的相同前后缀的长度。 ## 前缀函数 $\pi[i]$ 前缀函数 $\pi[i]$ 描述了一个字符串 $s$ 的子串 $s[0, i]$ 的最长相同前后缀的长度。也就是说，如果 $s[0, j]$ 是 $s[0, i]$ 的一个前缀，并且同时是其后缀，那么 $\pi[i] = j$。例如，对于字符串 "abcabc"，其前缀函数为 $\pi[0] = 0, \pi[1] = 0, \pi[2] = 0, \pi[3] = 1, \pi[4] = 2, \pi[5] = 3$。 ### 朴素算法实现 朴素的计算前缀函数的方法是遍历整个字符串，对于每个位置 $i$，从 $i$ 开始向回遍历，检查是否能找到相同的前后缀。这个算法的时间复杂度为 $O(n^2)$。 ### 优化算法 为了提高效率，可以通过利用已计算出的前缀函数 $\pi[i-1]$ 来优化。当 $\pi[i]$ 增大时，$\Delta\pi$（即 $\pi[i] - \pi[i-1]$）不会超过 1。因此，可以从 $\pi[i-1] + 1$ 开始尝试，直到找到满足条件的 $j$。这个优化后的算法的时间复杂度仍然是 $O(n)$。 ### 最终优化版本 最终的 KMP 算法中的前缀函数计算方式是： 1. 初始化 $j = \pi[i-1]$。 2. 当 $j > 0$ 且 $s[i] \neq s[j]$ 时，将 $j$ 更新为 $\pi[j-1]$，这相当于在前缀函数序列中回溯。 3. 如果 $s[i] = s[j]$，则将 $j$ 加 1，因为找到了一个更长的相同前后缀。 4. 将新的 $j$ 值赋给 $\pi[i]$。 ### KMP 模式匹配算法 KMP 算法基于前缀函数，避免了暴力算法中不必要的字符比较。在暴力算法中，当模式串（p）中的字符不匹配时，需要从头开始比较下一个字符，而 KMP 算法则能跳过不匹配的部分，继续进行匹配，从而大大提高了效率。其时间复杂度为 $O((p.length + s.length))$，其中 $p$ 是模式串，$s$ 是主串。 总结来说，前缀函数是解决字符串匹配问题的关键，通过高效地计算前缀函数，KMP 算法能在线性时间内完成模式匹配任务，极大地提升了性能。