如何找到字符串中的最長回文子串？

加入 LINE@ 趣聞不漏接

作者 |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：

/***@authorxiaoshion2018/9/24.*HappyMid-AutumnFestival*/publicclassPlalindromeString{//判斷一個字符串是否回文，算法中用不到了@DeprecatedprivatebooleanisPlalindrome(Strings){intlen=s.length();for(inti=0;i<len/2;i++){if(s.charAt(i)!=s.charAt(len-1-i)){returnfalse;}}returntrue;}//預處理字符串，在兩個字符之間加上#privateStringpreHandleString(Strings){StringBuffersb=newStringBuffer();intlen=s.length();sb.append('#');for(inti=0;i<len;i++){sb.append(s.charAt(i));sb.append('#');}returnsb.toString();}//尋找最長回文字串publicStringfindLongestPlalindromeString(Strings){//先預處理字符串Stringstr=preHandleString(s);//處理後的字串長度intlen=str.length();//右邊界intrightSide=0;//右邊界對應的回文串中心intrightSideCenter=0;//保存以每個字符為中心的回文長度一半（向下取整）int[]halfLenArr=newint[len];//記錄回文中心intcenter=0;//記錄最長回文長度intlongestHalf=0;for(inti=0;i<len;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]<rightSide){//直接推出結論needCalc=false;}}//中心擴展if(needCalc){while(i-1-halfLenArr[i]>=0&&i+1+halfLenArr[i]<len){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];}}}//去掉之前添加的#StringBuffersb=newStringBuffer();for(inti=center-longestHalf+1;i<=center+longestHalf;i+=2){sb.append(str.charAt(i));}returnsb.toString();}}

Main.java：

/***@authorlixinon2018/9/24.*/publicclassMain{publicstaticvoidmain(String[]args){PlalindromeStringps=newPlalindromeString();String[]testStrArr=newString[]{"abcdcef","adaelele","cabadabae","aaaabcdefgfedcbaa","aaba","aaaaaaaaa"};for(Stringstr:testStrArr){System.out.println(String.format("原字串:%s",str));System.out.println(String.format("最長回文串:%s",ps.findLongestPlalindromeString(str)));System.out.println();}}}

運行結果：

原字串:abcdcef最長回文串:cdc原字串:adaelele最長回文串:elele原字串:cabadabae最長回文串:abadaba原字串:aaaabcdefgfedcbaa最長回文串:aabcdefgfedcbaa原字串:aaba最長回文串:aba原字串:aaaaaaaaa最長回文串:aaaaaaaaa