给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
示例代码：
1 public class Test {
2 public static void main(String[] args) {
3 System.out.println(longestPalindrome("88111211109"));
4 }
5
6 public static char[] manacherString(String s){ //将字符串转化为长度为2*字符串长度+1的数组
7 char[] chars = new char[s.length()*2+1];
8 char[] chars1 = s.toCharArray();
9 int index=0;
10 for (int i = 0; i < chars.length; i++) {
11 chars[i] = (i&1)==0?'#': chars1[index++];
12 }
13 return chars;
14 }
15
16 public static String longestPalindrome(String s){
17 char[] chars = manacherString(s);
18 int start=0;
19 int end = 0;
20 int maxStart = 0;//记录最长回文字符串的初始索引
21 int maxEnd = 0;//记录最长回文字符串的末尾索引
22 int max=Integer.MIN_VALUE;//最大回文字符串长度
23 for (int i = 0; i < chars.length; i++) {
24 start = i;
25 end = i;
26 while (start>0&&end<chars.length-1&&chars[start-1]==chars[end+1]){//以每个遍历的字符为中心向左右两边扩展
27 start--;
28 end++;
29 }
30 int len=end-i;
31 if (len>max){
32 max=len;
33 maxStart = start;
34 maxEnd = end;
35 }
36 }
37
38 StringBuilder sb = new StringBuilder();
39 for (int i = maxStart; i < maxEnd; i++) {
40 if (chars[i] != '#') {
41 sb.append(chars[i]);
42 }
43 }
44
45 return sb.toString();
46 }
47
48
49 }
这段代码是用来查找字符串中最长回文子串的。它使用了 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"，并返回结果。
标签：子串,int,复杂度,最长,字符串,chars,回文 From： https://www.cnblogs.com/FangwayLee/p/17547434.html