最长回文子串
public class Manacher {
public static int min(int a, int b) {
return a < b ? a : b;
}
public static void manacher(char[] s, int[] p) {
int size = s.length;
p[0] = 1;
int id = 0;
int mx = 1;
for (int i = 1; i < size; i++) {
if (mx > i) {
p[i] = min(p[2 * id - i], mx - i);
} else {
p[i] = 1;
}
for (; (i + p[i] <= size - 1) && (s[i + p[i]] == s[i - p[i]]);) {
p[i]++;
}
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
}
}
public static void main(String[] args) {
String str = "ABCCBC";
char[] s = new char[str.length() * 2 + 2];
int[] p = new int[s.length];
s[0] = '$';
for (int i = 0; i < str.length(); i++) {
s[i * 2 + 1] = '#';
s[i * 2 + 2] = str.charAt(i);
}
s[s.length - 1] = '#';
manacher(s, p);
int index = 0;
int max = 0;
for (int i = 0; i < s.length; i++) {
if (p[i] > max) {
index = i;
max = p[i];
}
}
System.out.println("字符串"+str);
System.out.println("最长回文子串的位置为：" + (index - p[index]));
System.out.println("最长回文子串的长度为：" + (max - 1));
System.out.println("最长回文子串为：");
for (int i = index - p[index] + 1; i < index + p[index]; i++) {
if (i % 2 == 0) {
System.out.print(s[i]);
}
}
}
}
输出结果：
字符串ABCCBC
最长回文子串的位置为：2
最长回文子串的长度为：4
最长回文子串为：
BCCB
============================
字符串ABCDCBCDDE
最长回文子串的位置为：2
最长回文子串的长度为：5
最长回文子串为：
BCDCB
网友评论