给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
`public class Test { public static void main(String[] args) { System.out.println(longestPalindrome("88111211109")); }
public static char[] manacherString(String s){ //将字符串转化为长度为2*字符串长度+1的数组
char[] chars = new char[s.length()*2+1];
char[] chars1 = s.toCharArray();
int index=0;
for (int i = 0; i < chars.length; i++) {
chars[i] = (i&1)==0?'#': chars1[index++];
}
return chars;
}
public static String longestPalindrome(String s){
char[] chars = manacherString(s);
int start=0;
int end = 0;
int maxStart = 0;//记录最长回文字符串的初始索引
int maxEnd = 0;//记录最长回文字符串的末尾索引
int max=Integer.MIN_VALUE;//最大回文字符串长度
for (int i = 0; i < chars.length; i++) {
start = i;
end = i;
while (start>0&&end<chars.length-1&&chars[start-1]==chars[end+1]){//以每个遍历的字符为中心向左右两边扩展
start--;
end++;
}
int len=end-i;
if (len>max){
max=len;
maxStart = start;
maxEnd = end;
}
}
StringBuilder sb = new StringBuilder();
for (int i = maxStart; i < maxEnd; i++) {
if (chars[i] != '#') {
sb.append(chars[i]);
}
}
return sb.toString();
}
}`
这段代码是用来查找字符串中最长回文子串的。它使用了 Manacher 算法，该算法可以在线性时间内找到最长回文子串。
首先，manacherString 函数将输入字符串转换为长度为 2 * 字符串长度 + 1 的字符数组。它通过在每个字符之间插入 # 字符来实现这一点。例如，字符串 "abc" 将被转换为字符数组 ['#', 'a', '#', 'b', '#', 'c', '#']。
接下来，longestPalindrome 函数使用上面生成的字符数组来查找最长回文子串。它从左到右遍历字符数组，并对于每个位置，向左右两边扩展，直到不再是回文串为止。然后记录下最长的回文子串的起始和结束位置。
最后，函数使用 StringBuilder 来构建最终的回文子串，并返回结果。
例如，在上面给出的代码中，输入字符串为 "88111211109"，经过 manacherString 函数转换后的字符数组为 ['#', '8', '#', '8', '#', '1', '#', '1', '#', '1', '#', '2', '#', '1', '#', '1', '#', '1', '#', '0', '#', '9', '#']。然后，longestPalindrome 函数找到最长的回文子串为 "21112"，并返回结果。