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

ここからはパターン (表れるかを判定したい文字列) が複数の場合の PMA の構築をおこないます。
基本的な構築の流れはパターンが 1 つの場合と変わらず、パターンを格納したトライ木を構築し、さらに辺 failure を張ることで PMA を構築することができます。
Aho–Corasick 法をおこなうために次のような Node クラス, AhoCorasick クラスを作成してください。これらは問題「PMAの構築 1 」で作成したものと同じです。ただし、 build(): void の説明は後述します。

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 にする (本問題で実装)

Aho–Corasick 法では最初にパターンを格納したトライ木を構築した後、トライ木にを追加して PMA を構築します.
例えば、パターンを "ab", "ba", "bab", "cbab" とした場合のトライ木は次のようになります。図の赤い頂点はパターンに対応する頂点であること　(is_pattern が true であること)　を示しています。



ここに failure を張ります。この張り方もパターンが1つの場合と同じく、ある頂点 u から出る failure は、「u が対応する文字列 S の、 S を除く接尾辞の中でグラフ内に存在する最長の文字列 T の対応する頂点」へと引かれます。上のトライ木に failure を追加すると次の図のようになります。青い辺が failure を示しています。



この PMA を用いて同じようにパターンマッチングをおこないたいところですが、実はこれは不完全です。例えば、"cba" というテキストに対して上手くいきません。テキスト "cba" に対するパターンマッチングでは "ba" というパターンを検知するはずですが、頂点 cba が赤い頂点ではない (is_pattern が true ではない) ため検知することが出来ません。

ここで PMA の赤い枠で囲った部分に注目すると、頂点 cba から頂点 ba への failure が引かれており、その先の頂点 ba は赤いです。これをよく考えると、頂点 cba の対応する文字列も "ba" を含むことから頂点 cba も赤い頂点にしなければならないことが分かります。これをさらに広く捉えると failure の先の頂点が赤いなら、自身も赤くしなければならないことが分かります。なぜなら failure の「接尾辞に引く」という引き方から、failure の出る頂点の対応する文字列にはその先の頂点の対応する文字列が必ず接尾辞として含まれているからです。つまり、failure を引く際には failure の先の頂点が赤いなら、出ていく頂点も赤くする必要があります。また、PMA を構築した際に is_pattern は「パターンを含むか」を表すようになります。さらに根には全ての文字に対する遷移が定義されている必要があり、定義されていない文字に対しては自己ループとなる遷移を定義します。
これらを踏まえると正しい PMA は次の図のようになります。



注意点として failure を引くときには failure を引きたい頂点よりも浅い頂点の failure が根を除いて全て引かれている必要があります。これは次のトライ木から PMA を構築する例を考えると分かります。



PMA を構築した後には頂点 ba と頂点 cba はパターン "a" を含むため、赤くならなければなりません。
しかし、頂点 ba よりも先に頂点 cba の failure を引いてしまうと頂点 cba が赤くなることはありません。これを防ぐために、根に近い頂点から順に failure を引く必要があります。

AhoCorasick のメンバ関数 build() は次のような処理をおこないます。

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

入力としてパターンとする文字列 S_1, ..., S_N が与えられます。
これらの文字列を格納したトライ木を構築した後、トライ木に対して build() を実行して PMA を構築してください。
その後、各 S_i に対して順に次のような出力をおこなってください。
・S_i の長さ j の接頭辞を S_{i, j} と表記します。
・各 S_{i,j} (1 ≦ j ≦ |S_i|) の対応する頂点について、次の 2 つをこの順に、空白区切りで 1 行で出力してください。
出力 1： is_pattern が true なら Yes、そうでないなら No を出力してください。
出力 2： S_{i,j} から出る failure の行先の頂点の対応する文字列を出力してください。ただし、行き先が根である場合は EPS と出力してください。