扩展KMP算法：快速查找字符串匹配

"扩展KMP算法是一种在字符串匹配过程中寻找最长公共前后缀的优化算法，它基于原始的KMP算法并增加了对匹配过程的进一步分析。该算法的主要目标是找到字符串S中的所有子串与目标字符串T的最长匹配，并记录这些匹配的起始位置。 在扩展KMP算法中，关键概念是`extend[i]`，它表示字符串S的子串S[i]S[n-1]与T的最长相同前缀的长度。`extend[i]`的计算依赖于一个辅助数组`next[]`，这个数组存储的是T的每个子串与其自身的最长相同前缀的长度。例如，对于字符串T，`next[i]`表示T[i]T[m-1]与T的最长相同前缀的长度。 算法流程如下： 1. 初始化：计算`extend[0]`到`extend[i-1]`的值，并设置变量`a`和`p`。`p`表示以`a`为起始位置的字符匹配成功的最右边界，即`S[ap) = T[0p-a)`。 2. 使用`next[]`数组：对于每个`i`，通过`next[i-a]`来更新`extend[i]`。如果`i+next[i-a] < p`，那么`extend[i] = next[i-a]`，因为它们具有相同的前缀。 3. 匹配检查：如果`i+next[i-a] == p`，意味着可能存在匹配，但需要进一步比较S[p]和T[p-i]。如果它们不相等，可以直接从这两个位置开始继续匹配。 4. 跳过不匹配部分：如果`i+next[i-a] > p`，则S[p]肯定不等于T[p-i]，因此无需继续比较，可以直接将`extend[i]`设为`p-i`。 5. 计算`next[]`数组：`next[]`的计算是KMP算法的基础，通过对T的自比较找出每个位置的最长公共前后缀长度。 扩展KMP算法的优势在于它可以有效地处理多个匹配情况，而不仅仅是找到一个匹配的起始位置。通过提前计算`next[]`和`extend[]`数组，算法能够在匹配过程中避免不必要的比较，从而提高效率。 在C++中实现扩展KMP算法，需要创建`extend[]`和`next[]`数组，并根据上述规则动态更新。同时，需要维护一个指向S的指针和一个指向T的指针，进行字符的比较和匹配状态的更新。当找到一个匹配时，记录下匹配的起始位置，并继续查找下一个可能的匹配。 扩展KMP算法是字符串匹配算法的一个强大工具，尤其适用于需要找出所有匹配子串的情况。它通过巧妙地利用了字符串的前后缀关系，减少了比较次数，提高了搜索效率。"