[問題案] Aho Corasick

[yosupo06]

(任意) 問題ID: aho_corasick 問題名: Aho Corasick

問題概要

文字列がN個与えられる。 Aho CorasickのTrieを出力

入力

出力

制約

出力形式要検討

[maspypy]

問題文の下書き。

---

文字列 $S_1, \ldots, S_N$ が与えられます．これらからなる Trie のノードに次のようにして番号をつけます．

• $P_{i,j}$ を $Si$ の長さ $j$ の prefix とする．集合 $P$ を $\lbrace P{i,j}\mid i,j\rbrace$ で定める． $n=|P|$ とする．
• Trie のノード $v$ はある $str(v)=P_{i,j}$ に対応している．このような $(i,j)$ を辞書順に最小にとったときの $(i,j)$ が小さい順にノードに $0, 1, \ldots, n-1$ の番号をつける．

まず，Trie の情報を次の形式で出力してください

• $n$：集合 $P$ の要素数
• $p_0,p1,\ldots,p{n-1}$：親のノードの番号．ただし $p_0=-1$．
• $v{0,0},\ldots,v{0,n_0}$： $S0$ の prefix $S{0,j}$ に対応するノードの番号
• $\vdots$

さらに，suffix link の情報を次の形式で出力してください．

• $s_0,s1,\ldots,s{n-1}$：suffix link の番号．

Trie の頂点 $v\neq 0$ に対して，suffix link $w=s_v$ は ，$str(w)$ が $str(v)$ の proper suffix であるような $w$ のうちで $|str(w)|$ が最大のものとして定義します．ただし $s_0=-1$ と定めます．