Manacher
文字列$ Sについて、$ i文字目を中心とする最長回文の半径をすべての$ iについて全体$ O(|S|)で求める。
code: ex.py
a b a a a b a b a
1 2 1 4 1 2 3 2 1
半径を求めていることに注意。実際の回文長は$ 2r-1
code: Manacher.py
def Manacher(S):
"""
各iについて、iを中心とする最長の回文の半径をO(|S|)で求める。
"""
i, j = 0, 0
while i < len(S):
while i-j >= 0 and i+j < len(S) and Si-j == Si+j: j += 1 k = 1
while i-k >= 0 and k+Ri-k < j: k += 1
i += k
j -= k
return R
上のコードは奇数長の回文しか検出できないが、a$b$a$c$bのように$ Sの各文字の間にダミー文字を挟むことで偶数長の回文に対応できる。ただしそのまま使うとダミー文字を回文長に加えてしまうため補正が必要になる。
下は文字間の空白を含む全要素について、それを中心とする最長回文長を求めるコード。
code: Manacher_verify.py
S = input()
dummy_s = "$"
ST = []
ST.append(s)
ST.append(dummy_s)
R = Manacher(ST)
for i in range(len(R)):
else:
print(*R)
Verify
リファレンス