©2016-2024 Matools All rights reserved,
粤ICP备17059708号
package advanced_001; public class Code_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 C = -1; int R = -1; int max = Integer.MIN_VALUE; for
(int i = 0; i != charArr.length; i++) { pArr[i] = R > i ? Math.min(pArr[2 * C -
i], R - 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] > R) { R = i + pArr[i]; C = i; } max = Math.max(max, pArr[i]); }
return max - 1; } public static void main(String[] args) { String str1 =
"abc1234321ab"; System.out.println(maxLcpsLength(str1)); } }
Manacher's Algorithm 马拉车算法 <http://www.cnblogs.com/grandyang/p/4475985.html>
操作及原理
(解释的比较烦，大佬勿喷)
问题：查找一个字符串的最长回文子串 <http://en.wikipedia.org/wiki/Longest_palindromic_substring>
首先叙述什么是回文子串：回文：就是对称的字符串，或者说是正反一样的
小问题一：请问，子串和子序列一样么？请思考一下再往下看
当然，不一样。子序列可以不连续，子串必须连续。
举个例子，”123”
的子串包括1，2，3，12，23，123(一个字符串本身是自己的最长子串)，而它的子序列是任意选出元素组成，他的子序列有1，2，3，12，13，23，123，
””,空其实也算，但是本文主要是想叙述回文，没意义。
小问题二：长度为n的字符串有多少个子串？多少个子序列？
子序列，每个元素都可以选或者不选，所以有2的n次方个子序列（包括空）
子串：以一位置开头，有n个子串，以二位置开头，有n-1个子串，以此类推，我们发现，这是一个等差数列，而等差序列求和，有n*(n+1)/2个子串(不包括空)。
(这里有一个思想需要注意，遇到等差数列求和，基本都是o(n^2)级别的)
一、分析枚举的效率
好，我们来分析一下暴力枚举的时间复杂度，上文已经提到过，一个字符串的所有子串，数量是o(n^2)级别，所以光是枚举出所有情况时间就是o(n^2)，每一种情况，你要判断他是不是回文的话，还需要o(n)，情况数和每种情况的时间，应该乘起来，也就是说，枚举时间要o(n^3)，效率太低。
二、初步优化
思路：我们知道，回文全是对称的，每个回文串都会有自己的对称轴，而两边都对称。我们如果从对称轴开始，
向两边阔，如果总相等，就是回文，扩到两边不相等的时候，以这个对称轴向两边扩的最长回文串就找到了。
举例：1 2 1 2 1 2 1 1 1
我们用每一个元素作为对称轴，向两边扩
0位置，左边没东西，只有自己；
1位置，判断左边右边是否相等，1=1所以接着扩，然后左边没了，所以以1位置为对称轴的最长回文长度就是3；
2位置，左右都是2，相等，继续，左右都是1，继续，左边没了，所以最长为5
3位置，左右开始扩，1=1，2=2，1=1，左边没了，所以长度是7
如此把每个对称轴扩一遍，最长的就是答案，对么？
你要是点头了。。。自己扇自己两下。
还有偶回文呢，，比如1221，123321.这是什么情况呢？这个对称轴不是一个具体的数，因为人家是偶回文。
问题三：怎么用对称轴向两边扩的方法找到偶回文？（容易操作的）
我们可以在元素间加上一些符号，比如/1/2/1/2/1/2/1/1/1/，这样我们再以每个元素为对称轴扩就没问题了，每个你加进去的符号都是一个可能的偶数回文对称轴，此题可解。。。因为我们没有错过任何一个可能的对称轴，不管是奇数回文还是偶数回文。
那么请问，加进去的符号，有什么要求么？是不是必须在原字符中没出现过？请思考
其实不需要的，大家想一下，不管怎么扩，原来的永远和原来的比较，加进去的永远和加进去的比较。（不举例子说明了，自己思考一下）
好，分析一波时间效率吧，对称轴数量为o(n)级别，每个对称轴向两边能扩多少？最多也就o(n)级别，一共长度才n; 所以n*n是o(n^2)
(最大能扩的位置其实也是两个等差数列，这么理解也是o(n^2)，用到刚讲的知识)
小结：
这种方法把原来的暴力枚举o(n^3)变成了o(n^2),大家想一想为什么这样更快呢？
我在kmp一文中就提到过，我们写出暴力枚举方法后应想一想自己做出了哪些重复计算，然后进行优化。
看我们的暴力方法，如果按一般的顺序枚举，012345，012判断完，接着判断0123，我是没想到可以利用前面信息的方法，因为对称轴不一样啊，右边加了一个元素，左边没加。所以刚开始，老是想找一种方法，左右都加一个元素，这样就可以对上一次的信息加以利用了。
暴力为什么效率低？永远是因为重复计算，举个例子：12121211，下标从0开始，判断1212121是否为回文串的时候，其实21212和121等串也就判断出来了，但是我们并没有记下结果，当枚举到21212或者121时，我们依旧是重新尝试了一遍。(假设主串长度为n，对称轴越在中间，长度越小的子串，被重复尝试的越多。中间那些点甚至重复了n次左右，本来一次搞定的事）
还是这个例子，我换一个角度叙述一下，比较直观，如果从3号开始向两边扩，121，21212，最后扩到1212121，时间复杂度o(n),用枚举的方法要多少时间？如果主串长度为n，枚举尝试的子串长度为，3，5，7....n,等差数列，大家读到这里应该都知道了，等差数列求和，o(n^2)。
三、Manacher原理
和kmp不一样，我想了想，觉得manacher算法应该先讲原理再说code实现，因为方法或者code让萌新看了确实比较懵。
首先告诉大家，这个算法时间可以做到o(n),空间o(n).
好的，开始讲解这个神奇的算法。
首先明白两个概念：
最右回文边界R：挺好理解，就是目前发现的回文串能延伸到的最右端的位置(一个变量解决）
中心c：第一个取得最右回文边界的那个中心对称轴；举个例子:12121，二号元素可以扩到12121，三号元素
可以扩到121，右边界一样，我们的中心是二号元素，因为它第一个到达最右边界
当然，我们还需要一个数组p来记录每一个可能的对称轴最后扩到了哪里。
有了这么几个东西，我们就可以开始这个神奇的算法了。
为了容易理解，我分了四种情况，依次讲解：
假设遍历到位置i
i>R:也就是说，i以及i右边，我们根本不知道是什么，因为从来没扩到那里。那没有任何优化，直接往右暴力 扩呗。
（下面我们做i关于c的对称点，i’）
i<R:(这三种开始看图)，，(怕你忘了概念，再说一下吧，c是对称中心，c它当初扩到了R，R是目前扩到的最右的地方，现在咱们想以i为中心，看能扩到哪里。)按原来o(n^2)的方法，直接向两边暴力扩。好的，魔性的优化来了。咱们为了好理解，分情况说。首先，大家应该知道的是，i’其实有人家自己的回文长度，我们用数组p记录了每个位置的情况，所以我们可以知道以i
’为中心的回文串有多长）
i’的回文左边界在c回文的里面：看图
（画的很丑，不要介意啦，不影响理解的）
我用这两个括号括起来的就是这两个点向两边扩到的位置，也就是i和i’的回文串，为什么敢确定i回文只有这么长？和i’
一样？我们看c，其实这个图整体是一个回文串啊。串内完全对称(1是括号左边相邻的元素，2是右括号右边相邻的元素，34同理)
当初i’
为什么没有继续扩下去？因为1！=2，由整体回文可知，2=3，1=4，因为1！=2，所以3！=4，所以i也就到这里就扩不动了，但是34中间肯定是回文，因为整体回文，和12中间对称。
i’回文左边界在整体回文的外面了：看图
这时，我们也可以直接确定i能扩到哪里，请听分析：当初c的大回文，扩到R为什么就停了？因为2！=4不相等，2’为2关于i’的对称点，当初i’
左右为什么能继续扩呢？说明2=2’
，由c回文可知2’=3，所以2=3，但是2！=4，所以推出3！=4，所以i扩到34为止了，34不等。而34中间那一部分，因为c回文，和i’
在内部的部分一样，是回文，所以34中间部分是回文。
（解释的很委屈。。当面说很容易的）
最后一种当然是i’左边界和c左边界是一个元素，这就有点迷了：
1！=2，2=3，就能推出这些，只知道34中间肯定是回文，外边的呢？不知道啊，因为不知道3和4相不相等，所以我们得出结论：34内肯定是，然后暴力扩。
原理及操作叙述完毕，不知道我讲没讲明白。。。
四、代码及复杂度分析
看代码大家是不是觉得不像o(n)？其实确实是的，来分析一波。。
首先，我们的i依次往下遍历，而R（最右边界）从来没有回退过吧？其实当我们的R到了最右边，就可以结束了。再不济i自己也能把R一个一个怼到最右
我们看情况一和四，R都是以此判断就向右一个，移动一次需要o(1)
我们看情况二和三，直接确定了p[i]，根本不用扩，直接遍历下一个元素去了，每个元素o(1).
综上，由于i依次向右走，而R也没有回退过，最差也就是i和R都到了最右边，而让它们移动一次的代价都是o(1)的，所以总体o(n)
(全是自己根据理解写的啊。。可能叙述的不好，欢迎交流)
可能大家看代码依旧有点懵，其实就是code整合了一下，我们对于情况23，虽然知道了它肯定扩不动，但是我们还是给它一个起码是回文的范围，反正它扩一下就没扩动，不影响时间效率的。而情况四也一样，给它一个起码是回文，不用验证的区域，然后接着扩，四和二三的区别就是。二三我们已经心
中有B树，它肯定扩不动了，而四确实需要接着尝试。
（要是写四种情况当然也可以。。但是我懒的写，太多了。便于理解分了四种情况解释，code整合后就是这样子）
总，非正文：这算是和kmp一文一个系列吧，都是字符串类型，接下来我想写一些别的字符串类型题目的详解，但是有些题我又想放到动态规划优化里面写，反正最近要把知识总结一下，写出来，对自己也是一个提高，虽然这个过程挺烦的，没有直接当面讲那么容易，但是也算一种锻炼吧。
大佬们有什么建议给我说哈。
字数3411
范天祚
2017/12/22
热门工具 换一换