Manacher算法详解：寻找最长回文子串

Manacher算法是一种高效的算法，用于在字符串中寻找最长的回文子串。该算法的核心思想是在每个字符之间插入一个特殊符号，从而将奇数和偶数长度的回文子串统一处理。

### 基本概念

回文子串：一个字符串从前往后读和从后往前读是一样的。例如，"abcba"是一个回文子串。

回文半径数组：对于每个位置i，记录以i为中心的最长回文子串的半径长度。

最右回文右边界R：所有回文半径中，最靠右的位置。

回文右边界的中心C：当前回文右边界到达最右边时，是以哪个位置为中心进行扩充的。

### 算法步骤

1. **预处理**：在原字符串的每个字符之间插入一个特殊符号（如"#"），并在字符串的开头和结尾各加一个不同的特殊符号（如"^"和"$"），以避免越界问题。

2. **初始化**：定义两个变量C和R，分别表示当前回文右边界到达最右边时的中心位置和最右边界。

3. **遍历字符串**：对于每个位置i，计算其回文半径。

- **情况1**：如果i不在回文右边界R内，则采用暴力方法从i开始向两边扩展，直到不再形成回文子串。

- **情况2**：如果i在回文右边界R内，且i关于回文右边界中心C的对称位置i'的回文半径全部在L和R内部，则i位置的回文半径与i'相同。

- **情况3**：如果i在回文右边界R内，但i关于回文右边界中心C的对称位置i'的回文半径部分超出了R，则i位置的回文半径为R-i。

- **情况4**：如果i在回文右边界R内，且i关于回文右边界中心C的对称位置i'的回文半径部分超出了R，则从R+1开始继续扩展，直到不再形成回文子串。

4. **更新最右回文右边界R**：如果当前回文子串的右边界超过了R，则更新C和R。

### 示例

假设输入字符串为"abba"，经过预处理后变为"^#a#b#b#a#$"。按照上述步骤计算每个位置的回文半径，最终得到最长回文子串为"abba"。

### 总结

Manacher算法通过在字符间插入特殊符号，将奇数和偶数长度的回文子串统一处理，大大提高了查找效率。该算法的时间复杂度为O(n)，适用于各种长度的字符串。