求解回文字符串的算法,本库中直接给出回文字段的求解
Manacher解决的问题:求解回文字段
Manacher算法的核心是基于这样一个事实
j是i关于id的对称点,i位于id的回文字段内,则i的回文字段长度取决于j的回文字段长度
---------j--------id---------i--------
-mx-------------id--------------mx
回文半径:一个回文串中最左或最右位置的字符与其对称轴的距离
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
$ | # | a | # | b | # | b | # | a | # | h | # | o | # | p | # | x | # | p | # |
0 | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 2 | 1 |
很明显 p[i]-1最长回文串的长度
算法的实现分为如下几个步骤
为字符串b添加起始符号和间隔符号,得到处理后的字符串S
b="abbahopxp"
S="$#a#b#b#a#h#o#p#x#p#"
很明显,字符J的回文半径我们已知为p[j],id的回文半径为p[id],我们只需求出p[i]的回文半径即可
根据p[j]的长度,有如下三种情况可以讨论
- p[j]位于-mx以外,很明显,因为id为回文串,根据对称性,p[i]的长度至少为 [-mx,j],也就是mx-i
-p[j]---j---p[j]
-mx-------------id--------------mx
那p[i]的长度可以超过mx吗?显然不可以,如果p[i]的长度可以超过mx,那么根据对称性,p[id]左侧应该更长,显然不可以
这种情况下
p[i] = min(mx - i,p[j]) = mx - i
- p[j] 位于-mx 以内,很明显 p[i]的长度应该等于p[j]
-p[j]----j----p[j]
-mx-------------------id--------------------mx
那p[i]的长度可以更长吗?显然不可以 ,否则p[j]的长度应该更长
这种情况下
p[i] = min(mx-i,p[j]) = p[j]
- p[j] 恰好和-mx重合,很明显,p[i]的长度至少为p[j],也就是mx-i的长度
-p[j]----j----p[j]
-mx-------------------id--------------------mx
那么p[i]的长度可以更长吗,很明显可以
这种情况下 p[i] = min(mx-i,p[j])+... = p[j] + ...
id:=0
mx := p[id]+id
for i := 1; i < len(s); i++ {
//there are 2 situations:
// case 1:i<mx p[i] = min(mx-i,p[j])
// case 2:i>=mx,we do nothing
if i < mx {
p[i] = min(mx-i, p[2*id-i])
} else {
p[i] = 1
}
//find the LPS when i is the center
for i+p[i] < len(s) && s[i-p[i]] == s[i+p[i]] {
p[i]++
}
//update mx and id if the right board of LPS of i is biggerthan the right board of LPS of id
if i+p[i] > mx {
id = i
mx = id + p[id]
}
}