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

ここではパターン (表れるかを判定したい文字列) が複数の場合の PMA の構築をおこないます。
1 つ前の問題「PMAの構築 2 」ではある頂点の failure の行先を判定する際にその対応する文字列の接尾辞を全て調べる必要がありました。

実はこれよりも効率の良い PMA の構築方法があります。PMA では次の関係が成り立っています。



まず、failure を張りたい頂点を s とします。s は頂点 r から文字 α によって遷移できる頂点です。また、頂点 r の既に張られている failure の遷移先は頂点 p です。このとき、頂点 p から文字 α によって遷移できる頂点を q とします。今知りたいのは s の failure の行先ですが、これは頂点 q となります。
この図は r の接尾辞に α を付け足した文字列 s の接尾辞 q は、r の接尾辞 p に α を付け足した文字列 q となりえることを示しています。

例を用いて確認します。下に示す PMA の赤枠で囲った部分を例に示します。



今、頂点 cb が 頂点 r に対応し、頂点 cb から文字 a によって遷移できる頂点 cba が頂点 s に対応します。このとき、頂点 cb から failure によって遷移できる頂点 b が頂点 p に対応します。また、頂点 b　から文字 a によって遷移できる頂点 ba が頂点 q に対応しますが、この頂点は頂点 cba の接尾辞となっていることが確認できます。
この関係は他の頂点についても同様に成り立つことが確認できます。

この関係を用いる場合、頂点 r, s と文字 α が決まっているときに頂点 p を探すことになります。次のような PMA の赤枠部分に注目します。



今、頂点 abcd の failure を張りたいとします。つまり、頂点 abcd が頂点 s 、頂点 abc が頂点 r となります。このとき、p となる頂点を探したいです。頂点 abc から failure で遷移した頂点 bc には文字 d による遷移が定義されていません。そこで頂点 bc からさらにfailure による遷移をおこなうと、頂点 c にたどり着きます。この頂点には文字 d による遷移が定義されているので、頂点 c が p 、頂点 cd が q となり、頂点 cd が頂点 abcd からの failure の行先となります。

これらを踏まえると頂点 p は頂点 r から failure による遷移を繰り返して到達できる頂点の中で、文字 α による遷移が定義されている最初の頂点とすれば良いです。「最初の」とするのは q が、p の接尾辞のうち最長のものという failure の引き方の条件を満たすようにするためです。

頂点 s の failure の行き先となる頂点 q を知るための手順は次のようになります。

・効率的な failure の貼り方
初期設定として深さ 1 の頂点の failure を全て根に向かって貼る. 
その後, 幅優先探索の要領で根に近い順で failure がすでに張られている頂点に対して以下の処理を行う.
1. 今いる頂点を r とする.
2. r から文字 ch で遷移できる頂点があるならその頂点を s とする.
3. 文字 ch による遷移が定義されている頂点にたどり着くまで, 頂点 r から failure による遷移を繰り返す. たどり着いた頂点が p となる.
4. 頂点 p から文字 ch によって遷移する頂点が q となる.
5. s の failure を q に向かって貼る.

以前の問題で、複数のパターンを格納したトライ木から PMA を構築するメンバ関数 build(): void を書きましたが、上記の手順を用いて failure を張ることで PMA の構築をより高速におこなうことが出来ます。この手順を使ってbuild() を書き換えてください。

入力としてパターンとする文字列 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 と出力してください。