INFOPASS归来# Immigration - 落地生根
b*u
1 楼
仔细看了一遍 manacher's alg
http://leetcode.com/2011/11/longest-palindromic-substring-part-
逻辑判断上无法理解原版的
if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to
find P[ i ].
反而是stackoverflow 上第一个回复里的比较靠谱
http://stackoverflow.com/questions/10468208/manachers-algorithm
if P[i'] P[i]=P[i']
else if P[i']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
也就是说,只有恰好到达边缘的时候无法判断需要延伸,其余情况就是min(边缘距离,
对称点)
这个之前有人讨论过吗?还是已有定论了?
http://leetcode.com/2011/11/longest-palindromic-substring-part-
逻辑判断上无法理解原版的
if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to
find P[ i ].
反而是stackoverflow 上第一个回复里的比较靠谱
http://stackoverflow.com/questions/10468208/manachers-algorithm
if P[i']
else if P[i']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
也就是说,只有恰好到达边缘的时候无法判断需要延伸,其余情况就是min(边缘距离,
对称点)
这个之前有人讨论过吗?还是已有定论了?