一、背景
最近在LintCode上面刷题时遇到了一个求解最长回文子串的问题，这个题目可以使用暴力的方式去进行求解，但算法的时间复杂度至少就是O(n^2)级别了，后面看讨论区时发现了一个比较有意思的算法，也就是今天的主题－－Manacher算法，用这个算法可以只需要O(n)级别的时间复杂度，花时间去学习了一下，感觉确实是挺好的一种思路，这里就来记录一下。
二、算法过程
1.简介
Manacher算法是通过求解一个中心点，在距离这个点R长度以内都是关于这个点左右对称的，也就是说这个长度为2R的字符串是一个回文串，最后再比较大小，求出最大的长度2R及其中心点，最后就得出了题解，并且整个过程就扫描整个字符串一遍。这里也可以看出，因为要求回文子串的中心点，这个中心点也是唯一的，所以它只能处理字符串是奇数位的情况。因此我们第一步就是把字符串长度变为奇数，这里就要使用一个非常巧妙的方式，把字符串中每个字符使用一个其它字符号包围起来，，这里以“＃”号为例，可以想象一下，要把每个字符都使用''#''号包裹，那么需要的#号总是要比原来的字符串长度多一位，才能保证每个字符都能被插入到#与#中间，简单举个例子
aa -> #a#a#
aaa -> #a#a#a#
可以看到不管原来的字符串长度是什么，奇数加偶数结果肯定是奇数的，进行这一步处理后，就可以开始求最长回文子串的半径R了。
2.求解最长回文子串半径
这里可以先借助两个变量center、right分别记录回文子串对应的中心点和右端点，看看下图，
其实这里直接可以知道right就是2xcenter-i（也就是i关于center的对称点），既然是对称点，那么当端点right>i时，端点i需要进行计算回文子串R，但它的对称点有可能也进行过计算，所以可以无需从头开始匹配，因为这些点都包含在一个已经进行过匹配的父回文串中，所以这里可以直接取right-i和它的对称点回文子串半径长度较小的，用来保证绝对进行过计算的回文子串的部分;反之，就只能从1个长度开始匹配了，就是下面的这行代码，这里可能没如果还不理解的可以看看末尾的参考链接，这里我就不去画图了
r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;
这里借助一个辅助的数组r[]来记录回文子串的半径R，r[i]表示的是以i为中心点的回文字符串的半径长度(初始情况下为1)，知道r[i]后，就可以继续把索引向左右两边扩充，也就是看i+r[i]与i-r[i]左右端点的位置所对应的字符是否相等，相等的话就把回文半径r[i]继续扩充，直到不相等为止。进行这一轮扩充后，就去看看之前的右端点right是否小于回文子串扩充后的右端点i+r[i],小于就直接更新右端点和中心点，不小于就说明当前回文子串还是在当前right端点的内部。
3.全部代码
public class Test200 {
public String longestPalindrome(String s) {
// write your code here
StringBuilder builder = new StringBuilder();
// 防止左端点越界
builder.append("&#");
char[] c = s.toCharArray();
for (int i=0;i < c.length;i++) {
builder.append(c[i]+"#");
}
String newStr = builder.toString();
c = newStr.toCharArray();
// 回文半径
int[] r = new int[newStr.length()];
// 回文子串最大右端点、中心点
int right=0, center=0;
// 最大回文半径、最大中心点
int maxR=0, maxC=0;
for (int i=1;i < c.length;i++) {
// 以i为中心点的回文半径，可以重复利用以及匹配过对称点的半径
r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;
while (i+r[i]<c.length && c[i+r[i]]==c[i-r[i]]) {
++r[i];
}
// 更新右端点和中心点
if (right < i+r[i]) {
right = i+r[i];
center = i;
}
// 更新最大半径和最大中心点
if (maxR < r[i]) {
maxR = r[i];
maxC = i;
}
}
// 计算在原字符串中的起始点
int start = (maxC-maxR)/2;
return s.substring(start, start+maxR-1);
}
public static void main(String[] args) {
String s = "aa";
Test200 test = new Test200();
System.out.println(test.longestPalindrome(s));
}
}
三、总结
整体来说，理解清楚了，这个算法确实是挺巧妙的，就暂时到这里了。
参考：https://www.felix021.com/blog/read.php?2040
