唐高阳

【摘 要】本文首介绍了如何运用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数组每个位置的值的过程。……