这是悦乐书的第343次更新，是第367篇的原创
Manacher's Algorithm，中文称为马拉克算法。 一个叫Manacher的人在1975年提出的算法，解决了的问题是求出最长回文子串。 奇怪的是将算法的时间复杂度提高到了o(n )。 下面详细介绍该算法的思路。
01算法的由来
解决最长回文子串的问题时，一般的想法是以现在的文字为中心，向左右扩展寻找回文，但是这个解法的时间复杂度是o(n^2)，能再降低一点时间复杂度吗？ 线性的？ 马拉克算法完美地解决了这个问题。
02预处理
回文字符串按其长度可分为奇回文(其长为奇数)、偶回文(其长为偶数)，一般需要分两种情况查找回文。 马拉克算法为了简化这一步骤，会处理原始字符串，在每个字符的左右两侧添加特殊字符(一定是原始字符串中不存在的字符)，使字符串成为奇回文。 例如：
原始字符串： abba，长度为4
预处理后： #a#b#b#a#，长度9
原始字符串： aba，长度为3
预处理后： #a#b#a#，长度7
03最长回文部分列长的计算
以字符串' cabbaf '为例，将预处理后的新字符串' #c#a#b#b#a#f# '转换为一个字符数组arr，并定义辅助数组int[] p。 p的长度与arr相同，p[i]表示以arr[i]字符为中心的最长回文半径
i 0 1 2 3 4 5 6 7 8 9 10 11 12
arr[i] # c # a # b # b # a # f #
p[I]12121252121211111111
比较最大回文半径和原始字符串之间的关系吧。 在上述例子中，最长回文部分串是" #a#b#b#a# "，它以arr[6]为中心，半径为5，其代表性的原字符串是" abba "，" abba "的长度是4，从5到1
让我们看几个例子。 例如，' aba '，转换后以' #a#b#a# '，字符' b '为中心的回文，半径减去4，1得到3。 3是原始字符串的最长回文子串长度。
进而，在' effe '的情况下，变换后成为' #e#f#f#e# '，以最中间的' # '为中心的回文的半径为5，减去1得到4，4成为原字符串的最长回文部分列长。
因此，最后得到了最长回文半径与最长回文部分列长的关系： int maxLength=p[i]-1。 maxLength表示最长回文子串的长度。
04计算最长回文子串的开始索引
知道了最长回文子串的长度后，为了切出完整的最长回文子串，还需要知道其开始索引值。
就这一点来说，就拿步骤3中的字符串‘cab BAF’来说，p[6]=5是最长的半径，6(I )减去5 )5(p[i]就得到了1，这正好是最长的回复部分字符串‘ABBA’的开始索引
再看一个奇回文的例子吧。 例如' aba '，变换后得到' #a#b#a# '，p[3]=4，最长半径为4，I为3，I减去4，得到-1。 排列下标越界了。
偶回文时，可以从I中减去最大半径，但奇回文会越过下标。 需要在转换后的字符串前再增加一个字符，解决下标越界问题。 不能是“#”。 添加“$”字符吧。 但是，添加字符后，字符串的长度不是奇数。 只能在末尾添加不重复的文字。 例如，像“@”
增加一个字后，奇回文可以正常减法了，偶回文怎么样？
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13
arr[i] $ # c # a # b # b # a # f #
p[I]12121252121211111111
添加字符“$”后，p[7]=5，I减去最大半径，除以7-5=2，理想结果为1，那就除以2吧。 那样的话会得到1。 另一方面，奇回文' aba '是I减去最长半径除以0、2得到的结果为0，可以完美解决下标越界问题。
结论最长回文子串的起始索引intindex=(I-p[I] )/2。
05p数组的计算
在步骤3和步骤4中，我们使用了存储最长回文子串半径的关键对象p数组，它是怎么来的呢？
如果结合上面的例子来看，
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr[i] $ # c # a # b # b # a # f # @
p[I]12121252121211111111
设置两个变量id和mx。 id是所有回文子串中可以延伸到最右端位置的回文子串中心点的位置，mx是该回文子串可以延伸的最右端位置。
I为7时，id为7，p[id]=5，在以位置7为中心的回文子序列中，该回文子序列的右边界为位置12。
I为12时，为id等
于12，p[id] = 2，在以位置12为中心的回文子串中，该回文子串的右边界是位置14。由此我们可以得出回文子串右边界和其半径之间的关系：mx = p[id]+id。
image
因为回文字符串是中心对称的，知道中心点位置id，如果一个位置的回文子串以i为中心，并且包含在以id为中心的回文子串中，即mx > i，那么肯定会存在另外一个以j为中心回文子串，和以i为中心的回文子串相等且对称，即p[j] = p[i]，而i和j是以id为中心对称，即i+j=2*id，如果知道了i的值，那么j = 2*id - i。
但是我们需要考虑另外一种情况，如果存在一个以i为中心的回文子串，依旧有mx > i，但是以i为中心的回文子串右边界超过了mx，在i到mx的这段回文子串中，与另一端对称的以j为中心的回文子串还是相等的，此时p[i] = mx - i，p[j] = [pi]，至于右边界mx之外的子串，即以i为中心的回文子串超出的部分是否还是满足上述条件就需要遍历比较字符了。
因此，在mx > i的情况下，p[i] = Math.min(p[2*id - i], mx - i)。
另外如果i大于mx了，也即是边界mx后面的子串，依旧需要去比较字符计算。
public static String Manacher(String s) {
if (s.length() < 2) {
return s;
}
// 第一步：预处理，将原字符串转换为新字符串
String t = "$";
for (int i=0; i
t += "#" + s.charAt(i);
}
// 尾部再加上字符@，变为奇数长度字符串
t += "#@";
// 第二步：计算数组p、起始索引、最长回文半径
int n = t.length();
// p数组
int[] p = new int[n];
int id = 0, mx = 0;
// 最长回文子串的长度
int maxLength = -1;
// 最长回文子串的中心位置索引
int index = 0;
for (int j=1; j
// 参看前文第五部分
p[j] = mx > j ? Math.min(p[2*id-j], mx-j) : 1;
// 向左右两边延伸，扩展右边界
while (t.charAt(j+p[j]) == t.charAt(j-p[j])) {
p[j]++;
}
// 如果回文子串的右边界超过了mx，则需要更新mx和id的值
if (mx < p[j] + j) {
mx = p[j] + j;
id = j;
}
// 如果回文子串的长度大于maxLength，则更新maxLength和index的值
if (maxLength < p[j] - 1) {
// 参看前文第三部分
maxLength = p[j] - 1;
index = j;
}
}
// 第三步：截取字符串，输出结果
// 起始索引的计算参看前文第四部分
int start = (index-maxLength)/2;
return s.substring(start, start + maxLength);
}
06 小结
马拉车算法将求解最长回文子串的时间复杂度降低到了O(N)，虽然也牺牲了部分空间，其空间复杂度为O(N)，但是其算法的巧妙之处还是值得学习和借鉴的。
算法专题目前已连续日更超过六个月，算法题文章211+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，好看、留言、转发就是对我最大的回报和支持！