复习(重新学习)了一遍Manacher算法,比较靠谱的一篇讲解:
https://www.felix021.com/blog/read.php?2040。

主要思想:利用当前位置字符所在的已知最大回文串的对称性质,避免了对当前位置字符已知回文结构的检查。

1
2
3
4
5
6
7
8
9
C, R = 0, -1
for i in range(0, len(t)):
rad = min(p[2*C-i], R-i) if i <= R else 0
while i-rad-1>=0 and i+rad+1<len(t) and t[i-rad-1]==t[i+rad+1]:
rad += 1
p[i] = rad
if R < i+rad:
R = i+rad
C = i