manacher法 メモ

文字列sの各位置に対して、そこを中心とする回文の最長半径をO(|s|)で求める

 

やってることはかなりシンプルで、回文の対称性を使って調べた部分を使い回そうねという話

 

例:奇数長回文の場合

abcbaba

1131121

 

例:偶数長回文の場合は境界から見る

abccbabba

0003000200

 

 

ダミー文字は a$b$c より $a$b$c$ みたいに入れる方が好き

f:id:Hyado:20200326064530p:plain

 

参考文献

https://snuke.hatenablog.com/entry/2014/12/02/235837

 

verify

https://codeforces.com/contest/1326/problem/D2