Manacher算法

可以在时间复杂度为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]
最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方。

1. 第一种可能性
   
2. 第二种可能性
   
3. 第三种可能性
   

代码实现

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)); } }