如何找到字元串中的最长回文子串？

作者 | channingbreeze

责编 | 胡巍巍

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。可是努力了很久，别说BAT了，连TMD的橄榄枝都没有接到。

可是他越挫越勇。这不，今天他又去一家互联网小巨头公司面试了。

面试现场

小史：只要先对比第一个字元和倒数第一个字元，再对比第二个字元和倒数第二个字元，以此类推。如果都相等，那就是回文串了。

题目：给你一个字元串，找出里面最长的回文子串。

例如，输入abcdcef，那么输出应该是cdc；

输入adaelele，输出应该是elele。

半分钟过去了。

小史：可以遍历整个字元串，把每个字元和字元间的空隙当作回文的中心，然后向两边扩展来找到最长回文串。小史这次抢著分析时间和空间复杂度。

一分钟过去了。

请教大神

小史回到学校，把面试情况和吕老师说了一下。

吕老师：比如cabadabae用中心扩展的算法，我已经知道了第三位为中心的aba和第5位为中心的abadaba是回文，那么在判断第7位为中心的回文串的时候，有什么已知信息吗？

小史：已知第5位为中心的abadaba是回文，由回文的特性，就能够知道2-4位和6-8位对称，而又知道第3位为中心的aba是回文，所以2-4位是回文。这样的话，6-8位肯定是回文。

小史拿着笔在纸上画了半天，突然大叫一声。

小史：由于之前的计算，已经知道了第5位为中心的abadaba是回文，而第4位为中心的a的回文长度是1，所以第6位为中心的回文长度只能是1，不用再去扩展判断了。

小史：以第7位为中心的回文串的计算，由之前分析已经知道最小长度是3了，但是还是需要进行扩展，因为第9位是什么，根据之前的信息无法得知，需要扩展进行探索。

小史：而以第6位为中心的回文串的计算，并不需要进行探索了，因为根据之前第5位为回文中心串的信息、和第4位为回文中心串的信息，已经可以推断，第6位为回文中心串的长度只能为1。

小史：当然可以。

1、首先，我们要记录下目前已知的回文串能够覆盖到的最右边的地方，就像案例中的第8位

2、同时，覆盖到最右边的回文串所对应的回文中心也要记录，就像案例中的第5位

3、以每一位为中心的回文串的长度也要记录，后面进行推断的时候能用到，就像案例中用到的以第3位为中心的回文和第4位为中心的回文

4、对于新的中心，我们判断它是否在右边界内，若在，就计算它相对右边界回文中心的对称位置，从而得到一些信息，同时，如果该中心需要进行扩展，则继续扩展就行。

编码实现

小史：回文的中心有可能是两个字元中间，这种情况没有考虑到啊。

小史：

1、先对字元串进行预处理，两个字元之间加上特殊符号#；

2、然后遍历整个字元串，用一个数组来记录以该字元为中心的回文长度，为了方便计算右边界，我在数组中记录长度的一半（向下取整）；

3、每一次遍历的时候，如果该字元在已知回文串最右边界的覆盖下，那么就计算其相对最右边界回文串中心对称的位置，得出已知回文串的长度；

4、判断该长度和右边界，如果达到了右边界，那么需要进行中心扩展探索。当然，如果第3步该字元没有在最右边界的“羽翼”下，则直接进行中心扩展探索。进行中心扩展探索的时候，同时又更新右边界；

5、最后得到最长回文之后，去掉其中的特殊符号即可。

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

PlalindromeString.java：

/**

*@authorxiaoshi on 2018/9/24.

* Happy Mid-Autumn Festival

*/

publicclassPlalindromeString{

// 判断一个字元串是否回文，算法中用不到了

@Deprecated

privatebooleanisPlalindrome(String s){

intlen = s.length();

for(inti =; i

if(s.charAt(i) != s.charAt(len -1- i)) {

returnfalse;

}

}

returntrue;

}

// 预处理字元串，在两个字元之间加上#

privateStringpreHandleString(String s){

StringBuffer sb =newStringBuffer();

intlen = s.length();

sb.append("#");

for(inti =; i

sb.append(s.charAt(i));

sb.append("#");

}

returnsb.toString();

}

// 寻找最长回文字串

publicStringfindLongestPlalindromeString(String s){

// 先预处理字元串

String str = preHandleString(s);

// 处理后的字串长度

intlen = str.length();

// 右边界

intrightSide =;

// 右边界对应的回文串中心

intrightSideCenter =;

// 保存以每个字元为中心的回文长度一半（向下取整）

int[] halfLenArr =newint[len];

// 记录回文中心

intcenter =;

// 记录最长回文长度

intlongestHalf =;

for(inti =; i

// 是否需要中心扩展

booleanneedCalc =true;

// 如果在右边界的覆盖之内

if(rightSide > i) {

// 计算相对rightSideCenter的对称位置

intleftCenter =2* rightSideCenter - i;

// 根据回文性质得到的结论

halfLenArr[i] = halfLenArr[leftCenter];

// 如果超过了右边界，进行调整

if(i + halfLenArr[i] > rightSide) {

halfLenArr[i] = rightSide - i;

}

// 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了

if(i + halfLenArr[leftCenter]

// 直接推出结论

needCalc =false;

}

}

// 中心扩展

if(needCalc) {

while(i -1- halfLenArr[i] >=&& i +1+ halfLenArr[i]

if(str.charAt(i +1+ halfLenArr[i]) == str.charAt(i -1- halfLenArr[i])) {

halfLenArr[i]++;

}else{

break;

}

}

// 更新右边界及中心

rightSide = i + halfLenArr[i];

rightSideCenter = i;

// 记录最长回文串

if(halfLenArr[i] > longestHalf) {

center = i;

longestHalf = halfLenArr[i];

}

}

}

// 去掉之前添加的#

StringBuffer sb =newStringBuffer();

for(inti = center - longestHalf +1; i

sb.append(str.charAt(i));

}

returnsb.toString();

}

}

Main.java：

/**

* @author lixin on 2018/9/24.

*/

publicclassMain{

publicstaticvoidmain(String[] args){

PlalindromeString ps =newPlalindromeString();

String[] testStrArr =newString[] {

"abcdcef",

"adaelele",

"cabadabae",

"aaaabcdefgfedcbaa",

"aaba",

"aaaaaaaaa"

};

for(String str : testStrArr) {

System.out.println(String.format("原字串 : %s", str));

System.out.println(String.format("最长回文串 : %s", ps.findLongestPlalindromeString(str)));

System.out.println();

}

}

}

运行结果：

时间空间分析

作者简介：channingbreeze，国内某互联网公司全栈开发。

声明：本文为作者投稿，版权归对方所有。作者独立观点，不代表 CSDN 立场。

苹果手机的微信改版了，

想快速看到CSDN的热乎文章，

赶快把CSDN公众号设为星标吧，

打开公众号，点击“设为星标”就可以啦！

安卓手机的用户，

点击公众号右上角小人，就可以置顶啦。