Manacher Algorithm(马拉车算法理解)

Manacher Algorithm(马拉车算法)

一、 算法概述

Manacher算法(wikipedia)是求解字符串最长回文子串(Longest palindromic substring)问题的算法，它利用回文字符串和子回文字符串中观察到的一些特点，在线性时间内找出字符串的最长回文子串。这种算法能够尽可能利用之前探测回文子串时使用到的信息，进而避免一些不必要的探测。

Manacher算法，可以通过加入原本字符串中不存在的字符，将原本字符串回文子串长度为奇数和偶数两种情况统一起来。

Manacher算法会维护一个已经探测过的回文子串右边界最大的边界值。无论之前的信息是否可以利用，如果要进行新的探测，都只需从这个维护的边界向右探测。如果出现右边界位置更大的回文子串，则对其进行更新，这样以来，只需要O(n)的时间即可找到最长回文子串。

二、算法过程分析

1. 字符串预处理

在字符串的两边 和 相邻的两个字符之间 ，加入原本字符串中不存在的字符。将回文子串的长度为奇数和偶数统一起来。

• 如原字符串为： ababa ，处理之后的字符串为：#a#b#a#b#a#

• 为了能够使探测回文半径的循环遇到字符串边界时及时终止，退出循环，可在上述处理过的字符串两侧分别加入两个原字符串中没有且不同的字符。如上述处理过后的字符为： #a#b#a#b#a# ，首尾加入两个不同字符后为：$#a#b#a#b#a#!

• 注意这里新增的符号只要能够达到目的即可，不一定与此处保持一致

2. 原字符串与新字符串的关联

原本字符串的最长回文子串的长度是新字符串最长回文子串长度的一半(对2取整)。

因为按照预处理的规则，新字符串中得到的回文子串，无论原本字符串中回文子串长度为奇数还是偶数，处理之后得到的新回文串长度都为奇数。

• 如：abba 处理后得到 #a#b#b#a# 原长度为 4，新长度为 9。

• 如：aba 处理后得到 #a#b#a# 原长度为 3，新长度为 7。

• 不管原回文子串长度为奇为偶，加入的特殊字符(不含首尾两个)的个数总比其长度多 1，因此后续得到的回文串的长度总是奇数。

这样，由新的回文串得到原本的回文串长度，只需对 2 取整(/2)。

3. 如何利用之前已经获取到的信息？

3.1 维护数据

维护一个向量(或数组)f，其长度与处理之后得到的字符串相同，下标代表字符位置，值代表该位置回文半径长度。
维护两个变量：

• 当前右边界位置最大的回文串的 回文中心位置，初始化为 0

• 当前右边界位置最大的回文串的 右边界值，初始化为 0

3.2 按照规则进行初始化

3.2.1 如果当前计算的字符在前边得到的右边界值最大的