史先生是应届毕业生，学习电子专业，但自己在业余时间看了很多网络和编程方面的书，想进入BAT网络公司。
他今天又去网络大公司面试了。
【面试现场】
史(只需将第一个字符与倒数第一个字符进行比较，然后将第二个字符与倒数第二个字符进行比较即可。 如果都相等，那就是回文串。
主题：给个字符串，找出里面最长的回文的子串。
例如
如果输入abcdcef，则输出应该是cdc
输入adaelele。 输出必须为elele
一半过去了。
史)横跨整个字符串，以各字符和字符之间的间隙为回文中心，向两侧扩展可以找到最长回文串。
史先生这次正在分析时间和空间的复杂性。
一分钟过去了。
【请教大神】
史先生回到学校，讲述了面试的情况和灵巧的大豆。
灵巧大豆：比如cabadabae使用中心扩展的算法，知道以第三位为中心的aba和以第五位为中心的abadaba是回文，但是在判断以第七位为中心的回文串时，有什么已知的信息吗？
(史)已知以第5位为中心的abadaba是回文，从回文的特性可以看出，第2-4位和第6-8位是对称的，另外以第3位为中心的aba是回文，所以第2-4位是回文。 这样的话，第6-8名肯定是回文。
史先生拿着笔在纸上画了很久，突然大声喊道。
史)在此前的计算中，我们知道以第5位为中心的阿巴达比是回文，以第4位为中心的a的回文长度为1，所以以第6位为中心的回文长度只有1，没有必要扩展判断。
史)以第7位为中心的回文列的计算，从以前的分析中得知最小长度为3，但有必要进行扩展。 因为从以前的信息中不知道第9位是什么，所以有必要进行扩展探索。
小史：以第6位为中心的回文列的计算，不需要进行探索。 因为根据以前第5位是回文中心列的信息和第4位是回文中心列的信息，可以推测第6位是回文中心列的长度只有1。
历史：当然可以。
1、首先，像情况的第8位那样，记录现在已知的回文串能够覆盖的最右边的地方
2、同时，也记录与覆盖到最右边的回文列相对应的回文中心。 就像案例中的第五位一样
3、还记录以各位为中心的回文串的长度，以后估计时可以使用。 如案例中所用，以3位为中心的回文和以4位为中心的回文
4、对于新的中心，我们判断它是否在右边界内，如果有，计算相对于右边界回文中心的对称位置，得到一些信息，同时，如果其中心需要扩展，可以继续扩展。
【编码实现】
史：回文的中心可能是两个字的中间，但没有考虑到这种情况啊。
小史：
1、预处理字符串，在两个字符之间加特殊符号#
2、然后遍历整个字符串，用一个数组记录以该字符为中心的回文长度。 在数组中记录一半的长度，以便于计算右边界(
3、每次扫描时，如果该字符被已知回文串的最右边界复盖，则计算相对于最右边界回文串中心对称的位置，求出已知回文串的长度
4、需要判断其长度和右边界，到达右边界后进行中心扩展搜索。 当然，如果在步骤3中该字符不在最右边界的“羽翼”下，则直接进行中心扩展搜索。 进行中心扩展搜索时，同时更新右边界
5、最后得到最长回文后，只需去掉其中的特殊符号
理解算法后，小史的代码写得也很快，很快就写了：
PlalindromeString.java
/***@authorxia
oshi 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【时间空间分析】
面试现场是互联网侦察推出的一个新的板块，旨在回放真实的面试过程，并对面试题进行全面解析，提供多种思路，比较优劣，希望对大家的面试有所帮助。
往期回顾