Manacher算法在计算最长回文子串长度中的应用
2017-11-16唐高阳
唐高阳
【摘 要】本文首介绍了如何运用Manacher算法在线性时间内找到一个字符串的最长回文子串。
【关键词】Manacher算法；回文串；回文子串
The Manacher algorithm is used to calculate the length of the longest return string
TANG Gao-yang
（Shenyang institute of science and technology， Shenyang， Liaoning 110168）
【Abstract】This paper first introduces a method for finding the longest palindrome subsrting in linear time by the Manacher Algorithm.
【Key words】Manacher algorithm；Palindrome srting；Palindrome subsrting
1 遍历
因为奇回文和偶回文在判断时比较麻烦，所以对str进行处理，把每个字符开头、结尾和中间插入一个特殊字符′#′来得到一个新的字符串数组。比如str=″bcbaa″，处理后为″#b#c#b#a#a#″，然后从每个字符左右扩出去的方式找最大回文子串就方便多了。对奇回文来说，不这么处理也能通过扩的方式找到，比如″bcb″，从′c′开始向左右两侧扩出去能找到最大回文。处理后为″#b#c#b#″，从′c′开始向左右两侧扩出去依然能找到最大回文。对偶回文来说，不处理而直接通过扩的方式是找不到的，比如″aa″，因为没有确定的轴，但是处理后为″#a#a#″，就可以通过从中间的′#′扩出去的方式找到最大回文。所以通过这样的处理方式，最大回文子串无论是偶回文还是奇回文，都可以通过统一的“扩”过程找到，解决了差异性的问题。同时要说的是，这个特殊字符是什么无所谓，甚至可以是字符串中出现的字符，也不会影响最终的结果，就是一个纯辅助的作用。
具体的处理过程请参看如下代码中的manacherString方法。
public char[] manacherString（String str） {
char[] charArr=str.toCharArray（）；
char[] res=new char[str.length（）*2+1]；
int index=0；
for （i=0；I ！=res.length；i++）{
res[i]=（i&1）==0？#：charArr[index++]；
}
Return res；
}
2 优化
假设str处理之后的字符串记为charArr。对每个字符（包括特殊字符）都进行“优化后”的扩过程。
3 扩过程
只要能够从左到右依次算出数组pArr每个位置的值，最大的那个值实际上就是处理后的charArr中最大的回文半径，根据最大的回文半径，再对应回原字符串的话，整个问题就解决了。步骤3就是从左到右依次计算出pArr数组每个位置的值的过程。
（1）假设现在计算到位置i的字符charArr[i]，在i之前位置的计算过程中，都会不断地更新pR和index的值，即位置i之前的index这个回文中心扩出了一个目前最右的回文边界pR。
（2）如果pR-1位置没有包住当前的i位置。比如“#c#a#b#a#c#”，计算到charArr[1]==c时，pR为1。也就是说，右边界在1位置，1位置为最右回文半径即将到达但还没有达到的位置，所以当前的pR-1位置没有包住当前的i位置。此时和普通做法一样，从i位置字符开始，向左右两侧扩出去检查，此时的“扩”过程没有获得加速。
（3）如果pR-1位置包住当前的i位置。比如“#c#a#b#a#c#”，计算到charArr[6…10]时，pR都为11，此时pR-1包住了位置6-10。这种情况下，检查过程是可以获得优化的，这也是manacher算法的核心内容。
4 进阶问题
按照步骤3的逻辑从左到右计算出pArr数组，计算完成后再遍历一遍pArr数组，找出最大的回文半径，假设位置i的回文半径最大，即pArr[i]==max。但max只是charArr的最大回文半径，还得对应回原来的字符串，求出最大回文半径的长度（其实就是max-1）。在charArr中位置3的回文半径最大，最大值为4（即pArr[3]==4），对应原字符串的最大回文子串长度为4-1=3。
Manacher算法时间复杂度是O（N）的证明。虽然我们可以很明显地看到Manacher算法与普通方法相比，在扩出去检查这一行为上有明显的优化，但如何证明该算法的时间复杂度就是O（N）呢？关键之处在于估算扩出去检查这一行为发生的数量。原字符串在处理后的长度由N变为2N，从步骤3的主要逻辑来看，要么在计算一个位置的回文半径时完全不需要扩出去检查，比如，步骤3的中3）介绍的情况一和情况二，都可以直接获得位置i的回文半径长度；要么每一次扩出去检查都会让回文半径到达更右的位置，当然会使pR更新。然而pR最多是从-1增加到2N（右边界），并且从来不减小，所以扩出去检查的次数就是O（N）的级别。所以Manacher算法時间复杂度是O（N）。具体请参看如下代码中的maxLcpsLength方法。
public static int maxLcpsLength（String str） {
if （str == null || str.length（） == 0） {endprint
return 0；
}
char[] charArr = manacherString（str）；
int[] pArr = new int[charArr.length]；
int index = -1；
int pR = -1；
int max = Integer.MIN_VALUE；
for （int i = 0； i ！= charArr.length； i++） {
pArr[i] = pR > i ？ Math.min（pArr[2 * index - i]， pR - i） ： 1；
while （i + pArr[i] < charArr.length && i - pArr[i] > -1） {
if （charArr[i + pArr[i]] == charArr[i - pArr[i]]）
pArr[i]++；
else {
break；
}
}
if （i + pArr[i] > pR） {
pR = i + pArr[i]；
index = i；
}
max = Math.max（max， pArr[i]）；
}
return max - 1；
}
在字符串的最后添加最少字符，使整个字符串都成为回文串，其实就是查找在必须包含最后一个字符的情况下，最长的回文串是什么。那么之前不是最长回文子串的部分逆序过来，就是应该添加的部分。比如“abcd123321”，在必须包含最后一个字符的情况下，最长的回文子串是 “123321”，之前不是最长回文子串的部分是“abcd”，所以末尾应该添加的部分就是“dcba”。那么只要把manacher算法稍作修改就可以。具体改为：从左到右计算回文半径时，关注回文半径最右即将到达的位置（pR），一旦发现已经到达最后（pR == charArr.length），说明必须包含最后一个字符的最长回文半径已经找到，直接退出检查过程，返回该添加的字符串即可。具体过程参看如下代码中的shortestEnd方法。
public static String shortestEnd（String str） {
if （str == null || str.length（） == 0） {
return null；
}
char[] charArr = manacherString（str）；
int[] pArr = new int[charArr.length]；
int index=-1；
int pR=-1；
int maxContainsEnd = -1；
for （int i = 0； i ！= charArr.length； i++） {
pArr[i] = pR > i ？ Math.min（pArr[2 * index - i]， pR - i） ： 1；
while （i + pArr[i] < charArr.length && i - pArr[i] > -1） {
if （charArr[i + pArr[i]] == charArr[i - pArr[i]]）
pArr[i]++；
else {
break；
}
}
if （i + pArr[i] > pR） {
pR = i + pArr[i]；
index = i；
}
if （pR == charArr.length） {
maxContainsEnd = pArr[i]；
break；
}
}
char[] res = new char[str.length（） - maxContainsEnd + 1]；
for （int i = 0； i < res.length； i++） {
res[res.length - 1 - i] = charArr[i * 2 + 1]；
}
return String.valueOf（res）；
}
5 結果与分析
Manacher算法是由Glenn Manacher于1975年首次发明的，比起能够解决该问题的其他算法，Manacher算法算比较好理解和实现的。
【参考文献】
[1]Bruce Eckel.《Java编程思想》.机械工业出版社.2007.6.1.
[2]梁勇.《Java语言程序设计（基础篇）》.机械工业出版社2015.7.1.
[3]梁勇.《Java语言程序设计（进阶篇）》.机械工业出版社.2016.10.1.
[4]Thomas H.Cormen；Charles E.Leiserson；Ronald L.Rivest；Clifford Stein 《算法导论》机械工业出版社.2013.7.1.
[5]Mark Allen Weiss.《数据结构与算法分析 Java语言描述》.机械工业出版社.2009.1.1.
[6]Robert Sedgewick. Kevin Wayne.《算法（第4版）》人民邮电出版社.2012.10.1.endprint
