可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度在进行Manacher算法时字符串都会进行上面的进入一个字符处理比如输入的字符为acbbcbds用“#”字符处理之后的新字符串就是#a#c#b#b#c#b#d#s#回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度如下图所示对于p1所指的位置radius[6]的回文半径是5每个位置的回文半径组成的数组就是回文数组所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]最右回文右边界指的是这个位置及之前的位置的回文子串所到达的最右边的地方。第一种可能性第二种可能性第三种可能性代码实现public class Manacher { public static char[] manacherString(String str) { StringBuilder sb new StringBuilder(); for (int i 0; i str.length(); i) { sb.append(#); sb.append(str.charAt(i)); } sb.append(#); return sb.toString().toCharArray(); } public static int manacher(String str) { if (str null || str.length() 1) { return 0; } char[] charArr manacherString(str); int[] radius new int[charArr.length]; int R -1; int c -1; int max Integer.MIN_VALUE; for (int i 0; i radius.length; i) { radius[i] R i ? Math.min(radius[2 * c - i], R - i 1) : 1; while (i radius[i] charArr.length i - radius[i] -1) { if (charArr[i - radius[i]] charArr[i radius[i]]) { radius[i]; } else { break; } } if (i radius[i] R) { R i radius[i] - 1; c i; } max Math.max(max, radius[i]); } return max - 1; } public static void main(String[] args) { // String str abcdcbafabcdck; String str bcbbcbds; System.out.println(manacher(str)); } }
