來源：公衆號互聯網偵察

小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT互聯網公司。

今天他又去一家互聯網小巨頭公司面試了。

【面試現場】

小史：只要先對比第一個字符和倒數第一個字符，再對比第二個字符和倒數第二個字符，以此類推。如果都相等，那就是迴文串了。

題目：給你一個字符串，找出裏面最長的迴文子串。

例如

輸入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

/** * @author xiaoshi on 2018/9/24. * Happy Mid-Autumn Festival */public class PlalindromeString { // 判斷一個字符串是否迴文，算法中用不到了 @Deprecated private boolean isPlalindrome(String s) { int len = s.length(); for(int i = 0; i < len / 2; i++) { if(s.charAt(i) != s.charAt(len - 1 - i)) { return false; } } return true; } // 預處理字符串，在兩個字符之間加上# private String preHandleString(String s) { StringBuffer sb = new StringBuffer(); int len = s.length(); sb.append('#'); for(int i = 0; i < len; i++) { sb.append(s.charAt(i)); sb.append('#'); } return sb.toString(); } // 尋找最長迴文字串 public String findLongestPlalindromeString(String s) { // 先預處理字符串 String str = preHandleString(s); // 處理後的字串長度 int len = str.length(); // 右邊界 int rightSide = 0; // 右邊界對應的迴文串中心 int rightSideCenter = 0; // 保存以每個字符爲中心的迴文長度一半（向下取整） int[] halfLenArr = new int[len]; // 記錄迴文中心 int center = 0; // 記錄最長迴文長度 int longestHalf = 0; for(int i = 0; i < len; i++) { // 是否需要中心擴展 boolean needCalc = true; // 如果在右邊界的覆蓋之內 if(rightSide > i) { // 計算相對rightSideCenter的對稱位置 int leftCenter = 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]; } } } // 去掉之前添加的# StringBuffer sb = new StringBuffer(); for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) { sb.append(str.charAt(i)); } return sb.toString(); }}

Main.java

/** * @author lixin on 2018/9/24. */public class Main { public static void main(String[] args) { PlalindromeString ps = new PlalindromeString(); String[] testStrArr = new String[] { "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(); } }}

運行結果：

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

【時間空間分析】