public String longestPalindrome(String s){ int len = s.length(); String res = ""; for (int i = 0; i < len * 2 - 1; i++) { int left = i / 2; int right = left + i % 2; while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) { String tmp = s.substring(left, right + 1); if (tmp.length() > res.length()) { res = tmp; } left--; right++; } } return res; }
//给定一个字符串,返回它的最长回文字串长度 publicstaticintmanacher(String str){ if (str == null || str.length() == 0) { return0; } //将字符串扩展为manacher字符串(每个字符中间和字符串前后加#) //因为扩展后字符串长度翻倍,因此求扩展后的字符串的最大回文半径,即求原来字符串的最大回文直径 char[] charArr = manacherString(str); //pArr为回文半径数组 int[] pArr = newint[charArr.length]; int C = -1; int R = -1; //max记录最长的回文半径长度 int max = Integer.MIN_VALUE; for (int i = 0; i != charArr.length; i++) { //i在R里时:对于情况2和3,在i'的回文半径和i与R的距离中取较小值,即为i的回文半径 //对于情况4,先将回文半径设为R-i,再在之后while循环中将回文半径继续向外扩展 //i在R外时,先将i位置的回文半径置为1,之后再在while循环里扩展 pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; //情况2和情况3即使进入了该while循环,但是第一次if都不会成立,会直接break退出循环 //只有情况1和情况4会在while循环里进行回文半径的扩展。 while (i + pArr[i] < charArr.length && i - pArr[i] > -1) { if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) pArr[i]++; else { break; } } //更新最大回文右边界R和其对应的回文中心C if (i + pArr[i] > R) { R = i + pArr[i]; C = i; } //更新max max = Math.max(max, pArr[i]); } return max - 1; }
//生成manacher字符串,将给定字符串str的两端和每个字符中间全加上特殊符号# publicstaticchar[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = newchar[str.length() * 2 + 1]; int C = 0; for (int i = 0; i != res.length; i++) { res[i] = (i & 1) == 0 ? '#' : charArr[C++]; } return res; }