Manacher算法是一种用于找出给定字符串中最长的回文字符子串的算法.该算法的神来之笔是: 用一个不会出现在该目标字符串中的特殊字符对目标字符串进行填充, 为描述简便, 我们就假设该特殊符号为"#", 并且算法是从字符串的左端向右端开始寻找.
我们这样来完成填充:
1)在目标字符串的每个字符前面都塞入一个"#";
2)在目标字符串的末端加一个"#".
如此一来, 任意字符串"***"填充之后都会变成这个样子"#*#*#*#"
从填充的两个步骤可以看出, 任意长度为n的字符串, 在填充之后长度都会变成n+n+1, 即2n+1, 也就是说填充之后得到的字符串的长度一定是奇数.
由于后面不可避免地要讨论字符的位置下标, 所以从这里开始, 我们就把被填充后的字符串看做一个字符数组, 如果被填充前的目标字符串长度为n, 那么该字符数组的下标显然就是从0开始, 到2n结束. 同时为了后续描述的统一和便于理解, 我们在这个字符数组的基础上定义几个代名词:
当前有效回文字符串: 它是指当前已经找到的, 拥有最大右端下标的回文字符串, 注意, 它不一定是已经找到的最长回文字符串.
mPoint: middle point, 它是指当前有效回文字符串的中点字符的下标. mPoint的初始值是0, 它会逐渐右移.
radius: 回文字符串半径, 由于回文字符串是关于中点位置对称的, 所以把长度为n的回文字符串的半径定义为从中点位置分割后, 任意一侧的字符串长度+1(要把中点位置的字符算进去), 即n/2 + 1. 请注意: Manacher算法第一步所做的填充, 其神奇之处在这里开始显现, 因为从填充后的字符串中找出的最长回文字符串的长度也一定是奇数, 并且radius-1就是原始字符串中回文字符串的长度, 比如:
原字符串是"bbad", 我们可以找到的最长回文字符串是长度为2(偶数)的"bb"
而由于填充之后的字符串是"#b#b#a#d#", 所以我们可以找到的最长回文字符串就变成了长度为5(奇数)的"#b#b#" (半径为3, 减1恰好等于2)
原字符串是"cabad", 我们可以找到的最长回文字符串是长度为3(奇数)的"aba"
而由于填充之后的字符串是"#c#a#b#a#d#", 所以我们可以找到的最长回文字符串就变成了长度为7(仍为奇数)的"#a#b#a#" (半径为4, 减1恰好等于3)
数组P: 构造一个数组P, 用于记录字符数组中每个元素以其为中点可以形成的最大回文字符串的半径
rPoint: right point, 它是指当前有效回文字符串的右端字符的下标+1(注意我们是从左端开始检查的), rPoint = mPoint+P[mPoint]. rPoint的作用是利用回文字符串的特性, 减少不必要的检查, 后面会详述. rPoint的初始值是0, 它会逐渐右移
Manacher算法开始:
第一步, 初始化:
令 i = 0 (当前检查的字符下标), mPoint=0, rPoint = 0
第二步:
判断不等式①i < rPoint , 亦即确认当前检查的字符是否落在了当前有效回文字符串内
如果不等式①不成立, 说明当前还没有找到回文字符串, 或者当前有效回文字符串的半径没有覆盖到当前检查的字符, 则令radius = 1开始检查, 由于radius = 1, 即只包含当前元素本身, 必然立即找到以当前字符为中点第一个回文字符串(即它自己), 更新P[i] = 1
如果不等式①成立, 说明之前的检查已经找到了当前有效回文字符串, 并且其半径覆盖到了当前检查的字符, 也可以说当前检查的字符落在了当前有效回文字符串内
那么 i 一定有一个关于当前有效回文字符串的中点即 mPoint 的对称点, 我们称它为 j
作为同在当前有效回文字符串内的两个对称点, 在不超出当前有效回文字符串的左右两端的前提下, 注意这里要强调不超出, 我们不难想象, 如果以 j 为中点可以形成一个回文字符串, 那么一定也可以以 i 为中点形成一个相同的回文字符串(否则就不对称, 当前有效回文字符串就不可能存在).
于是我们可以整理下目前已经直接或者间接知道的事实:
(1) P[j]中已经存储了以 j 这个元素为中点可以形成的最长回文字符串半径
(2) 当前有效回文字符串是以mPoint为中心可以形成的最长回文字符串, 也就是说以mPoint为中心, 不可能再有更长的回文字符串, 并且其半径已经存储在了P[mPoint]中
(3) 如果回文字符串内部对称位置上有两个回文子串, 那么这两个回文子串必然是相同的
进而我们可以有以下推导(请读者不妨拿出笔和纸画一画线段图, 帮助理解):
a. 当 P[j]>rPoint-i 时, 也就是说以 j 这个元素为中点形成的最长回文字符串足以延伸至当前有效回文字符串左端以外时, 则一定有P[i] = rPoint-i, 因为如果P[i] > rPoint-i, 说明以 i 这个元素为中点形成的最长回文字符串足以延伸至当前有效回文字符串右端以外, 那么当前有效回文字符串就应该有更长的半径, 但这与事实(2)矛盾了. 而如果P[i] < rPoint-i, 则在当前有效回文字符串内部就会出现不对称使其不能成为回文字符串, 这同样产生矛盾.
b. 当P[j]<rPoint-i时, 也就是说以 j 这个元素为中点形成的最长回文字符串完全被包裹在当前有效回文字符串内部时, 则一定有P[i] = P[j], 否则它与事实(3)矛盾
以上两种情况就可以直接得出P[i], 无需任何检查!
c. 当P[j] = rPoint-i时呢? 这时只能确定P[i]应至少等于rPoint-i, 否则会与事实(3)矛盾, 可是P[i]可以更大, 这时我们才需要令radius=rPoint-i开始检查(这就比令radius = 1开始检查高效)
以当前元素为中点, 半径为radius开始检查回文字符串, 如果是回文字符串则扩展半径radius, 尝试寻找更长的回文字符串, 直至失败
此时要满足两个条件:
②扩展半径之后, 左端和右端的下标不越界.
③当前左端和右端的元素字符相同.
如果条件②和③都成立,则P[i] = P[i] + 1
紧接着判断不等式④i+P[i] > rPoint
如果④成立, 说明当前回文字符串的右端已经延伸到了更靠右的位置, 即产生新的当前有效回文字符串
立即更新mPoint为当前的 i , rPoint为i+P[i]
mPoint=i
rPoint=i+P[i]
如果P[i]比已知的最大回文字符串半径都大, 记录并更新最大半径(根据最终需求结果不同也可能是记录mPoint和rPoint的下标),
循环执行直至②或③不成立
第三步
i 自增, 重复执行第二步, 直至 i 到达字符数组的最有端(当然如果从 i 的位置不可能再找到比当前最长回文字符串更长的回文字符串时, 就可以提前结束)
