Palindromic Tree の追加

[rogi52]

文字列に含まれる全てのユニークな回文を求めるアルゴリズム。Trie木に似た木構造と Suffix Link からなるオートマトンを構築する。

文字の種類数を $k$、文字列 $s$ の長さを $n$ として

• オートマトンの構築: $O(kn)$ 空間・ $O(n)$ 時間
• 回文頻度表: $O(n)$
• 文字列の末尾に文字 $c$ を追加する: $O(1)$

参考資料

• http://adilet.org/blog/palindromic-tree/
• https://math314.hateblo.jp/entry/2016/12/19/005919
• https://mojashi.hatenablog.com/entry/2017/07/17/155520
• https://miti-7.hatenablog.com/entry/2016/03/14/195721

テスト問題

• https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2292&lang=jp
• https://yukicoder.me/problems/399 (↑の制約強化版)

[rogi52]

Trie木 や Aho-Corasick法 の実装方針にできるだけ寄せた実装を目標とします。