IT知识课堂TB▲求最长回文子串算法——马拉车算法( 二 ) Manacher'sAlgorithm

05计算p数组
在第三步和第四步中我们都用到了一个关键对象p数组，存放的是最长回文子串半径，那么它是怎么来的呢？还是以上面的例子配合着看，
i01234567891011121314
arr[i]$#c#a#b#b#a#f#@
p[i]1212125212121
设置两个变量id和mx ， id是所有回文子串中，能延伸到最右端位置的那个回文子串的中心点位置， mx是该回文串能延伸到的最右端的位置。
当i等于7时， id等于7 ， p[id]=5 ，在以位置7为中心的回文子串中，该回文子串的右边界是位置12 。
当i等于12时， id等于12 ， p[id]=2 ，在以位置12为中心的回文子串中，该回文子串的右边界是位置14 。
由此我们可以得出回文子串右边界和其半径之间的关系：mx=p[id]+id 。

文章图片
image
因为回文字符串是中心对称的，知道中心点位置id ，如果一个位置的回文子串以i为中心，并且包含在以id为中心的回文子串中，即mx>i ，那么肯定会存在另外一个以j为中心回文子串，和以i为中心的回文子串相等且对称，即p[j]=p[i] ，而i和j是以id为中心对称，即i+j=2*id ，如果知道了i的值，那么j=2*id-i 。
但是我们需要考虑另外一种情况，如果存在一个以i为中心的回文子串，依旧有mx>i ，但是以i为中心的回文子串右边界超过了mx ，在i到mx的这段回文子串中，与另一端对称的以j为中心的回文子串还是相等的，此时p[i]=mx-i ， p[j]=[pi] ，至于右边界mx之外的子串，即以i为中心的回文子串超出的部分是否还是满足上述条件就需要遍历比较字符了。
因此，在mx>i的情况下， p[i]=Math.min(p[2*id-i],mx-i) 。另外如果i大于mx了，也即是边界mx后面的子串，依旧需要去比较字符计算。

文章图片

文章图片
06小结
马拉车算法将求解最长回文子串的时间复杂度降低到了O(N) ，虽然也牺牲了部分空间，其空间复杂度为O(N) ，但是其算法的巧妙之处还是值得学习和借鉴的。