小史是一個(gè)應(yīng)屆生，雖然學(xué)的是電子專業(yè)妒峦，但是自己業(yè)余時(shí)間看了很多互聯(lián)網(wǎng)與編程方面的書重斑，一心想進(jìn)BAT互聯(lián)網(wǎng)公司。
今天他又去一家互聯(lián)網(wǎng)小巨頭公司面試了肯骇。
【面試現(xiàn)場(chǎng)】
小史：只要先對(duì)比第一個(gè)字符和倒數(shù)第一個(gè)字符窥浪，再對(duì)比第二個(gè)字符和倒數(shù)第二個(gè)字符，以此類推笛丙。如果都相等漾脂，那就是回文串了。
題目：給你一個(gè)字符串胚鸯，找出里面最長(zhǎng)的回文子串骨稿。
例如
輸入abcdcef，那么輸出應(yīng)該是cdc
輸入adaelele姜钳，輸出應(yīng)該是elele
半分鐘過(guò)去了。
小史：可以遍歷整個(gè)字符串哥桥，把每個(gè)字符和字符間的空隙當(dāng)作回文的中心辙浑，然后向兩邊擴(kuò)展來(lái)找到最長(zhǎng)回文串。
小史這次搶著分析時(shí)間和空間復(fù)雜度拟糕。
一分鐘過(guò)去了判呕。
【請(qǐng)教大神】
小史回到學(xué)校，把面試情況和呂老師說(shuō)了一下已卸。
呂老師：比如cabadabae用中心擴(kuò)展的算法佛玄，我已經(jīng)知道了第三位為中心的aba和第5位為中心的abadaba是回文硼一，那么在判斷第7位為中心的回文串的時(shí)候累澡，有什么已知信息嗎？
小史：已知第5位為中心的abadaba是回文般贼，由回文的特性愧哟，就能夠知道2-4位和6-8位對(duì)稱奥吩，而又知道第3位為中心的aba是回文，所以2-4位是回文蕊梧。這樣的話霞赫，6-8位肯定是回文。
小史拿著筆在紙上畫了半天肥矢，突然大叫一聲端衰。
小史：由于之前的計(jì)算已經(jīng)知道了第5位為中心的abadaba是回文，而第4位為中心的a的回文長(zhǎng)度是1甘改，所以第6位為中心的回文長(zhǎng)度只能是1旅东，不用再去擴(kuò)展判斷了。
小史：以第7位為中心的回文串的計(jì)算十艾，由之前分析已經(jīng)知道最小長(zhǎng)度是3了抵代，但是還是需要進(jìn)行擴(kuò)展，因?yàn)榈?位是什么根據(jù)之前的信息無(wú)法得知忘嫉，需要擴(kuò)展進(jìn)行探索荤牍。
小史：而以第6位為中心的回文串的計(jì)算，并不需要進(jìn)行探索了庆冕，因?yàn)楦鶕?jù)之前第5位為回文中心串的信息和第4位為回文中心串的信息已經(jīng)可以推斷第6位為回文中心串的長(zhǎng)度只能為1康吵。
小史：當(dāng)然可以。
1愧杯、首先涎才，我們要記錄下目前已知的回文串能夠覆蓋到的最右邊的地方，就像案例中的第8位
2力九、同時(shí)耍铜，覆蓋到最右邊的回文串所對(duì)應(yīng)的回文中心也要記錄，就像案例中的第5位
3跌前、以每一位為中心的回文串的長(zhǎng)度也要記錄棕兼，后面進(jìn)行推斷的時(shí)候能用到，就像案例中用到的以第3位為中心的回文和第4位為中心的回文
4抵乓、對(duì)于新的中心伴挚，我們判斷它是否在右邊界內(nèi)，若在灾炭，就計(jì)算它相對(duì)右邊界回文中心的對(duì)稱位置茎芋，從而得到一些信息，同時(shí)蜈出，如果該中心需要進(jìn)行擴(kuò)展田弥，則繼續(xù)擴(kuò)展就行。
【編碼實(shí)現(xiàn)】
小史：回文的中心有可能是兩個(gè)字符中間铡原，這種情況沒(méi)有考慮到啊偷厦。
小史：
1商叹、先對(duì)字符串進(jìn)行預(yù)處理，兩個(gè)字符之間加上特殊符號(hào)#
2只泼、然后遍歷整個(gè)字符串剖笙，用一個(gè)數(shù)組來(lái)記錄以該字符為中心的回文長(zhǎng)度，為了方便計(jì)算右邊界请唱，我在數(shù)組中記錄長(zhǎng)度的一半（向下取整）
3弥咪、每一次遍歷的時(shí)候，如果該字符在已知回文串最右邊界的覆蓋下十绑，那么就計(jì)算其相對(duì)最右邊界回文串中心對(duì)稱的位置酪夷，得出已知回文串的長(zhǎng)度
4、判斷該長(zhǎng)度和右邊界孽惰，如果達(dá)到了右邊界晚岭，那么需要進(jìn)行中心擴(kuò)展探索。當(dāng)然勋功，如果第3步該字符沒(méi)有在最右邊界的“羽翼”下坦报，則直接進(jìn)行中心擴(kuò)展探索。進(jìn)行中心擴(kuò)展探索的時(shí)候狂鞋，同時(shí)又更新右邊界
5片择、最后得到最長(zhǎng)回文之后，去掉其中的特殊符號(hào)即可
理解了算法之后骚揍，小史的代碼寫起來(lái)也是非匙止埽快，不一會(huì)兒就寫好了：
PlalindromeString.java
/**
*@authorxiaoshi?on?2018/9/24.
*?Happy?Mid-Autumn?Festival
*/
publicclassPlalindromeString{
//?判斷一個(gè)字符串是否回文信不，算法中用不到了
@Deprecated
privatebooleanisPlalindrome(String?s){
intlen?=?s.length();
for(inti?=0;?i?<?len?/2;?i++)?{
if(s.charAt(i)?!=?s.charAt(len?-1-?i))?{
returnfalse;
}
}
returntrue;
}
//?預(yù)處理字符串嘲叔，在兩個(gè)字符之間加上#
privateStringpreHandleString(String?s){
StringBuffer?sb?=newStringBuffer();
intlen?=?s.length();
sb.append('#');
for(inti?=0;?i?<?len;?i++)?{
sb.append(s.charAt(i));
sb.append('#');
}
returnsb.toString();
}
//?尋找最長(zhǎng)回文字串
publicStringfindLongestPlalindromeString(String?s){
//?先預(yù)處理字符串
String?str?=?preHandleString(s);
//?處理后的字串長(zhǎng)度
intlen?=?str.length();
//?右邊界
intrightSide?=0;
//?右邊界對(duì)應(yīng)的回文串中心
intrightSideCenter?=0;
//?保存以每個(gè)字符為中心的回文長(zhǎng)度一半（向下取整）
int[]?halfLenArr?=newint[len];
//?記錄回文中心
intcenter?=0;
//?記錄最長(zhǎng)回文長(zhǎng)度
intlongestHalf?=
0;
for(int?i?=?0;?i?<?len;?i++)?{
//?是否需要中心擴(kuò)展boolean?needCalc?=?true;
//?如果在右邊界的覆蓋之內(nèi)if(rightSide?>?i)?{
//?計(jì)算相對(duì)rightSideCenter的對(duì)稱位置int?leftCenter?=?2*?rightSideCenter?-?i;
//?根據(jù)回文性質(zhì)得到的結(jié)論
halfLenArr[i]?=?halfLenArr[leftCenter];
//?如果超過(guò)了右邊界，進(jìn)行調(diào)整if(i?+?halfLenArr[i]?>?rightSide)?{
halfLenArr[i]?=?rightSide?-?i;
}
//?如果根據(jù)已知條件計(jì)算得出的最長(zhǎng)回文小于右邊界抽活，則不需要擴(kuò)展了if(i?+?halfLenArr[leftCenter]?<?rightSide)?{
//?直接推出結(jié)論
needCalc?=
false;
}
}
//?中心擴(kuò)展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;
//?記錄最長(zhǎng)回文串if(halfLenArr[i]?>?longestHalf)?{
center?=?i;
longestHalf?=?halfLenArr[i];
}
}
}
//?去掉之前添加的#
StringBuffer?sb?=
newStringBuffer();
for(int?i?=?center?-?longestHalf?+?1;?i?<=?center?+?longestHalf;?i?+=?2)?{
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("最長(zhǎng)回文串?:?%s",?ps.findLongestPlalindromeString(str)));
System.out.println();
}
}
}
運(yùn)行結(jié)果：
原字串?:?abcdcef
最長(zhǎng)回文串?:?cdc
原字串?:?adaelele
最長(zhǎng)回文串?:?elele
原字串?:?cabadabae
最長(zhǎng)回文串?:?abadaba
原字串?:?aaaabcdefgfedcbaa
最長(zhǎng)回文串?:?aabcdefgfedcbaa
原字串?:?aaba
最長(zhǎng)回文串?:?aba
原字串?:?aaaaaaaaa
最長(zhǎng)回文串?:?aaaaaaaaa
【時(shí)間空間分析】
擴(kuò)展閱讀
【面試現(xiàn)場(chǎng)】如何實(shí)現(xiàn)可以獲取最小值的棧硫戈？
【面試現(xiàn)場(chǎng)】如何在10億數(shù)中找出前1000大的數(shù)
【面試現(xiàn)場(chǎng)】為什么要分穩(wěn)定排序和非穩(wěn)定排序？
來(lái)源：互聯(lián)網(wǎng)偵察
