ACM竞赛模板：Manacher算法实现O(n)求解最长回文子串

"ACM比赛模板积累，介绍Manacher算法，一种用于求解字符串最长回文子串的高效算法，时间复杂度为O(n)。" Manacher算法是一种在线性时间内寻找字符串最长回文子串的算法，由Manacher在1975年提出。这个算法巧妙地利用了回文串的对称性，避免了重复计算，从而大大提高了效率。在给定的描述和代码中，我们可以看到Manacher算法的主要步骤和实现细节。 1. **算法原理**： - Manacher算法的关键在于维护一个名为`pt`的数组，其中`pt[i]`表示以位置`i`为中心的回文子串的半径。 - 在处理过程中，算法会尝试扩展回文子串，如果当前位置`i`的回文子串能与之前找到的回文子串重叠，那么可以直接借鉴之前回文子串的信息，即`pt[i] = min(pt[(id<<1)-i], mx-i)`，其中`id`是上一个回文子串的中心，`mx`是上一个回文子串的最右侧边界。 - 在扩展过程中，若发现新的回文子串覆盖了之前的最大回文子串，就更新`mx`和`id`。 - 记录当前最大回文半径`mav`及其中心`v`，最终`mav`即为最长回文子串的长度。 2. **代码解析**： - `Manacher`函数接受两个字符串参数，`st1`是原始输入字符串，`st2`是处理后的字符串，中间插入了特殊字符`'#'`以便处理奇偶长度的回文子串。`'$'`字符用于区分字符串的边界。 - 首先，将输入字符串`st1`转换为`st2`，在每个字符之间插入`'#'`，并在首尾添加`'$'`，使得所有回文子串都能找到对应的对称中心。 - 然后，初始化`pt`数组，`mx`和`id`变量，遍历`st2`，根据对称性扩展回文子串，并更新`pt`、`mx`和`id`。 - 最后，`mav`减1得到最长回文子串的实际长度，然后输出最长回文子串的内容。 3. **应用场景**： - Manacher算法常用于ACM/ICPC等编程竞赛，以及实际的字符串处理问题，如文本分析、数据挖掘等领域，当需要快速找出字符串中的最长回文子串时，Manacher算法能提供高效的解决方案。 4. **性能分析**： - 时间复杂度：Manacher算法的时间复杂度为O(n)，其中n是输入字符串的长度。这是因为每个位置的回文半径只扩展一次，不会进行多次回溯。 - 空间复杂度：由于使用了辅助数组`pt`，空间复杂度也为O(n)。 通过理解Manacher算法的原理和代码实现，我们可以快速地在给定字符串中找到最长的回文子串，这对于处理大量字符串数据时具有很高的实用价值。