文章参考:
江湖人称:马拉车算法
解决的问题:求一个字符串中的最长回文。
暴力的方法:遍历字符串,以当前字符为中心,向两边扩展直至不是回文。时间复杂度O(n^2)
Manacher算法:是记录并利用以前遍历过的回文,巧妙的达到一个加速的效果。时间复杂度O(n)
首先了解三个概念:
(1)回文半径数组:已求的回文的半径存储起来,为后面可以起到加速效果,避免重复的运算。
(2)最右回文半径:已求出来的回文中,最右边的回文半径
(3)最右回文半径的中心:顾名思义
图解一下流程:
C:是最右回文半径的中心,R:已经求出的最右回文半径的位置点,L:R关于C的对称点。
i:为当前遍历的下标位置,i' :关于C的对称点(前面遍历,已经求出来的回文半径)。
第一种情况:i' 的回文都在(L~R)里面,直接得到 i 的回文半径就是 i' 的回文半径。如下图:
第二种情况:i' 的回文超出了(L~R)范围,部分在外面,直接得到 i 的回文半径就是 i 到 R的距离。如下图:
第三种情况:i' 的回文半径左边位置恰好与 L 重合,i 就从R边界开始,向外扩,得到 i 的回文半径。
第四种情况:是 i 在 R 的右边,不在(L ~ R)的里面。方法是暴力向外扩。
以上就是所有的情况。
代码:
package basic_class_02;public class Code_04_Manacher { public static char[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = new char[str.length() * 2 + 1]; int index = 0; for (int i = 0; i != res.length; i++) { res[i] = (i & 1) == 0 ? '#' : charArr[index++]; } return res; } public static int maxLcpsLength(String str) { if (str == null || str.length() == 0) { return 0; } char[] charArr = manacherString(str); int[] pArr = new int[charArr.length]; // 存储回文半径 int index = -1; // 最右回文边界的中心点 int pR = -1; // 最右回文边界 int max = Integer.MIN_VALUE; for (int i = 0; i != charArr.length; i++) { pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1; while (i + pArr[i] < charArr.length && i - pArr[i] > -1) { if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) pArr[i]++; else { break; } } if (i + pArr[i] > pR) { pR = i + pArr[i]; index = i; } max = Math.max(max, pArr[i]); } return max - 1; } public static void main(String[] args) { String str1 = "abc1234321ab"; System.out.println(maxLcpsLength(str1)); }}