Manacher算法详解

Manacher算法是一种高效的算法，用于在O(n)时间内找到字符串中的最长回文子串。本文将详细介绍该算法的原理和实现步骤。

### 算法原理

Manacher算法的核心思想是对字符串进行预处理，使其所有的回文子串都具有奇数长度，从而简化后续的处理过程。

#### 预处理步骤

(1) 在每个字符之间插入一个特殊的分隔符（例如#），这样可以将所有可能的奇数或偶数长度的回文子串转换为奇数长度的回文子串。例如，字符串“abba”变为“#a#b#b#a#”，字符串“aba”变为“#a#b#a#”。这样做可以统一处理不同长度的回文子串。

(2) 为了简化边界处理，可以在字符串的开头添加一个特殊的字符（例如$），这样可以避免在处理过程中出现越界的情况。例如，字符串“$#a#b#a#”。

#### 动态规划数组P[i]

定义一个数组P[i]，用于记录以字符S[i]为中心的最长回文子串的半径（包括S[i]）。例如，对于字符串“12212321”，经过预处理后变为S[] = “$#1#2#2#1#2#3#2#1#”，对应的P数组为：

可以看出，P[i]-1正好是原字符串中回文子串的总长度。

### 计算P[i]的步骤

算法引入了两个辅助变量id和mx，其中id表示当前已知的最大回文子串的中心位置，mx表示该回文子串的右边界（即id + P[id]）。

#### 处理过程

(1) 如果当前处理的字符i在mx的范围内（即mx > i），则可以利用之前的结果来加速计算。具体来说，设j = 2 * id - i，即j是i关于id的对称点。此时，P[i]的值可以通过以下方式确定：

• 如果mx - i > P[j]，则P[i] = P[j]。
• 如果mx - i <= P[j]，则P[i] = mx - i，但需要进一步匹配以确定最终的P[i]。

(2) 如果当前处理的字符i不在mx的范围内（即mx <= i），则需要从头开始逐个匹配，初始化P[i] = 1，然后逐步扩展回文子串的范围。

### 代码实现

通过上述步骤，Manacher算法能够在O(n)时间内找到字符串中的最长回文子串，适用于各种实际应用场景。