Manacher——最长回文子串
1. Manacher是干什么的？
Manacher算法是一个用来查找一个字符串中的最长回文子串(不是最长回文序列)的线性算法。它的优点就是把时间复杂度为O(n^2)的暴力算法优化到了O(n)。
2. 原始方法
在没有学会Manacher算法之前，查找最长回文子串的方法就是纯暴力的匹配。根据每一个当前字符，向左右扩展。
- 先不去判断对与错，单从这种算法上来讲，就已经是O(n^2)。
- 其次，如果是偶回文就不是那么好判断了，比如abba，不能过滤出回文子串。
3. Manacher含义
Manacher和KMP是一个意思，都是基于暴力匹配做了一些加速操作，有那么点DP的意思。但是Manacher判断回文子串的时候还做一些预处理。
3.1. 预处理
预处理主要是为了判断偶回文，以前的abba无法处理，但是经过Manacher的预处理后，就会变得格外的不同。
private char[] process(char[] chs){//重新声明一个字符数组//length == chs.length*2 + 1 ?char[] c = new char[chs.length*2 + 1] ;int index = 0 ;for (int i=0 ; i<c.length ; i++){c[i] = (i&1) == 0 ? '#' : chs[index++] ;}return c ;}
- char[] c：新创建的数组
- length == chs.length*2+1：需要将abba处理成 #a#b#b#a# ，为什么要处理成这个亚子？是因为要给偶回文找一个对称轴。
大致的逻辑就是这个样子，预处理这块代码很好懂。
3.2. Manacher核心部分
先上代码，后面讲解
public int manacher(String str){if (str == null || str.length() == 0){return 0 ;}char[] chs = process(str.toCharArray()) ;int l = chs.length ;//下面介绍的四个属性int index = -1 ;int pR = -1 ;int[] pArr = new int[l] ;int max = Integer.MIN_VALUE ;for (int i=0 ; i<l ; i++){//更新当前位置的初始化半径区域pArr[i] = pR > i ? Math.min(pArr[2*index-i] , pR - i) : 1 ;//左右扩充while(i + pArr[i] < l && i - pArr[i] > -1){if (chs[i+pArr[i]] == chs[i-pArr[i]]){pArr[i]++ ;}else{break ;}}//更新中心点和最右边界if (i + pArr[i] > pR){pR = i + pArr[i] ;index = i ;}//更新maxmax = max < pArr[i] ? pArr[i] : max ;}return max - 1 ;}
四个要素
- index：中心点位置
- pArr[]：每个位置的回文半径
- pR：最右可到达的回文半径，和index相对应
- max：回文半径最大值
有了这四个属性，理解Manacher还会远吗？
3.3. 大体流程
- 处理原始数据
- 第一种情况，i > pR 暴力扩
- 第二种情况，i < pR && pArr[i] + i < pR 也就是当前位置的右半径没有超过最右半径
- 第三种情况，i < pR && pArr[i] + i > pR 也就是当前位置的右半径超过最右半径
按照流程我们一步一步的走
首先是index=-1 pR=-1 i=0，为了方便，我先把pArr数组写好了。
- i = 0 时，说明i大于pR，需要暴力扩，pArr[0] = 1 ，
基本上就是按照三种情况进行的。
我们进行跳步
- 当 i = 5 时，状态如下图，可以看出index就是pR的中心点。i对应i`的半径2，说明#a#不需要再遍历了。接着就是向外扩了。可以左右扩到#b#a#b#，所以pArr[5]就等于4。然后更新index和pR，最后更新max。
3.4. 扩展的条件
扩展的条件就是while循环的条件，i + pArr[i] < l && i - pArr[i] > -1 。
- 第一个条件很好理解，就是当前位置i + 他的半径要小于整个数组的长度。
- 第二个条件可以这么看，
i > pArr[i] -1这个是保证左边界不出界。
3.5. 加速运动
加速运动体现在哪里，就是以index为中心点的 i 的对称点 **i ` ** 。
如果 i 在index 和 pR 中间，那么 i 的对称点就是 i’ 。所以将i‘ 的信息直接拿过来用就可以。但是需要做一些处理，也就是
min(pArr[2*index-i] , pR - i)。为什么?因为 在以index为中心，pR为半径的区域内，可以保证 i 和 i’ 是相对应的。如果大于pR的范围，是不保证pArr对应的。
4. 总结
Manacher其实有一部分DP的思想在里面，但是还是基于暴力破解。