PMAの構築 1 (paizaランク B 相当)

Aho–Corasick 法 (エイホーコラシック法) では PMA (パターンマッチングオートマトン) と呼ばれるグラフを作り、PMA 上を移動することでパターンマッチングをおこないます。パターンマッチングをおこなう文字列 (テキスト) の長さを L とすると、必要な計算量は O(L) と極めて高速です。

この問題ではパターン (表れるかを判定したい文字列) が１つの場合の PMA の構築を学びます。

最初にパターンを格納したトライ木を構築します。
例えば "abab" をパターンとした場合のトライ木は次の図のようになります。



トライ木の各頂点には「ある文字 ch を受け取ったときの遷移」 が定義されている場合があり、これを表しているのが図中の有向辺となります。ある頂点で文字 ch をラベルとして持つ出ていく辺があるなら、その頂点で文字 ch を受け取ったときにどの頂点に遷移するかが定義されています。文字 ch をラベルとして持つ出ていく辺がないならその頂点で文字 ch を受け取ったときの遷移は定義されてません。
ここで、根 (図の最も左にある、文字の書かれていない頂点) を始点として有向辺に沿ってある頂点 u に移動したとします。そして、通った経路のラベルを順に読んで得られる文字列を S とします。このとき、u を「S に対応する頂点、または単に頂点 S」と呼びます。各頂点に書かれている文字列が対応する文字列です。根は長さ 0 の文字列に対応します。また、根から u への経路で得られる文字列 S を「u に対応する文字列、または単に文字列 u」と呼びます。赤い頂点はパターンに対応する文字列であることを示しています。


次にこのトライ木に failure と呼ばれる有向辺を追加することで PMA を構築することができます。
PMA の根以外の頂点は自身を始点とする failure を必ず 1 つ持ちます。
長さ N の文字列の先頭 x (0 ≦ x ≦ N) 文字を削った文字列を接尾辞と言います。
例えば "abc" の接尾辞は "abc", "bc", "c", "" (長さ 0 の文字列) の 4 つです。
ある頂点 u から出る failure は、「u が対応する文字列 S の、 S を除く接尾辞の中で、グラフ内に存在する最長の文字列 T の対応する頂点」へと引かれます。
上に示したトライ木の各頂点に対して failure の行き先を探索し、 PMA を構築すると次の図のようになります。青い有向辺が failure を表しています。





本問題ではトライ木を構築し、failure を適切に引くことで PMA の構築をおこなってもらいます。
最初に次のような Node クラス、 AhoCorasick クラスを作成してください。問題「トライ木の構築」 で作成した Trie クラスを変更すると良いです。

Nodeクラス  //PMAの各頂点を表すクラス
-----------------------------------
メンバ変数
child[ch]: chをキーとして、頂点を返す連装配列   //文字 ch に対する遷移
failure: Node  //failure の遷移先の頂点
is_pattern: bool  //この頂点はパターンを受理するか(trueなら受理する)

AhoCorasickクラス  //PMA全体を表すクラス
-----------------------------------
メンバ変数
root: Node  //トライ木の根を表す
-----------------------------------
メンバ関数
insert(pattern: string): void //引数とする文字列 pattern をトライ木に挿入する
build(): void  //トライ木の各頂点に failure を引いて PMA にする (本問題で実装)

メンバ関数 insert() はトライ木に文字列を格納する処理です。
メンバ関数 build() は次のような処理をおこないます。

・根から到達できる全ての頂点とその対応する文字列を列挙する.
たどり着いた頂点では以下の処理をおこなう.
1. 頂点 S にたどり着いたなら, S を除く S の接尾辞を全て列挙する.
2. 列挙した接尾辞の対応する頂点がグラフ内に存在するかを調べる.
3. 存在する頂点の中で最も対応する文字列が長いものを頂点 S の failure の行先とする.

入力としてパターンとする文字列 S が与えられます。
S を格納したトライ木を構築した後、トライ木に対して build() を実行して PMA を構築してください。
その後、深さ 1 から深さ |S| の頂点まで順に failure の行き先となる頂点の名前を出力してください。ただし、行き先が根である場合は EPS と出力してください。
深さ x の頂点とは根から x 本の辺を通ってたどり着ける頂点のことです。