# 算法 – 找最长回文字符串, 从3s到30ms的解法说明

1. 找到所有的子字符串
2. 判断所有的子字符串是否是回文字符串
3. 统计回文子字符串的长度
4. 排序找出最长的那个

@Test
public void test() {
long l = System.currentTimeMillis();
// 共999个e
String s =
"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
System.out.println("字符串长度: " + s.length() + " 结果: " + longestPalindrome0(s));
long l1 = System.currentTimeMillis();
System.out.println("用时: " + (l1 - l) + "ms");
}

public String longestPalindrome0(String s) {
if (s == null || s.equals("")) return "";
if (s.length() == 1) return s;
int maxLength = 0;
String ns = "";
// 找出所有的子串
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
// 两层循环找出所有的子串
String s1 = s.substring(i, j);
// 判断是回文字符串
int len = s1.length() % 2 == 0 ? s1.length() / 2 : s1.length() / 2 + 1;
boolean b = false;
for (int k = 0; k < len; k++) {
// 通过比较第一个和倒数最后一个, 第二个和倒数第二个...是否相等判断是否是回文字符串
b = s1.substring(k, k + 1).equals(s1.substring(s1.length() - 1 - k, s1.length() - k));
// 如果碰到有一对不一样, 直接break, 省一些时间
if (!b) break;
}
if (b) {
// 如果是回文字符串, 跟先前保存的长度做比较, 如果比先前保存的回文字符串长度长, 则替换
if (maxLength < s1.length()) {
maxLength = s1.length();
ns = s1;
}
}
}
}
return ns;
}

public String longestPalindrome(String s) {
if (s == null || s.equals("")) return "";
if (s.length() == 1) return s;
int maxLength = 0;
String ns = "";
// 找出所有的子串
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
// 封装成StringBuilder对象
StringBuilder s1 = new StringBuilder(s.substring(i, j));
// 使用reverse()方法判断是否是回文字符串, 下面逻辑就跟上面那种解法一样了
if (s1.toString().equals(s1.reverse().toString())) {
if (maxLength < s1.length()) {
maxLength = s1.length();
ns = s1.toString();
}
}
}
}
return ns;
}

public String longestPalindrome1(String s) {
if (s == null || s.equals("")) return "";
char[] chars = s.toCharArray();
// 插入字符
String ns = "^#";
for (int i = 0; i < chars.length; i++) {
ns = ns + chars[i] + "#";
}
ns += "\$";
char[] chars1 = ns.toCharArray();
int[] p = new int[chars1.length];
boolean b;
int j = 1;
int maxLength = 0;
String ns1 = "";
// 只循环第2到倒数第二之间的字符串
for (int i = 1; i < chars1.length - 1; i++) {
b = true;
while (b) {
// 从当前循环的字符开始,往两边查找字符比较
char c1 = chars1[i - j];
char c2 = chars1[i + j];
if (c1 == c2) {
// 比较通过, 则+1
p[i] = p[i] + 1;
j++;
} else {
// 不通过, 开始统计最大数, 当当前比较次数比之前记录的比较次数大, 则更新上面的记录变量
if (maxLength < p[i]) {
maxLength = p[i];
ns1 = ns.substring(i - j + 1, i + j);
}
j = 1;
b = false;
}
}
}
// 最后别忘了把#去掉
return ns1.replace("#", "");
}