問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
ここからはパターン (表れるかを判定したい文字列) が複数の場合の 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 にする (本問題で実装)
PMA
を構築します.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" を含むため、赤くならなければなりません。failure
を引いてしまうと頂点 cba が赤くなることはありません。これを防ぐために、根に近い頂点から順に failure
を引く必要があります。AhoCorasick
のメンバ関数 build()
は次のような処理をおこないます。幅優先探索の要領で根から到達できる全ての頂点とその対応する文字列を列挙する.
たどり着いた頂点では以下の処理をおこなう.
1. 頂点 S にたどり着いたなら, S を除く接尾辞を全て列挙する.
2. 列挙した接尾辞の対応する頂点がグラフ内に存在するかを調べる.
3. 存在する頂点の中で最も対応する文字列が長いものを頂点 S の failure の行先とする.
4. failure の行先の is_pattern が true なら, 頂点 S の is_pattern も true にする.
build()
を実行して PMA
を構築してください。is_pattern
が true
なら Yes
、そうでないなら No
を出力してください。 EPS
と出力してください。
N
S_1
...
S_N
(i, j) が辞書順昇順となる順番で各 S_{i,j} に対する答えを出力してください。
このとき、S_{i,j} に対する 2 つの出力を出力 1、出力 2 の順に、空白区切り 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします
・1 ≦ N ≦ 100
・S_i (1 ≦ i ≦ N) は英小文字のみで構成される
・1 ≦ |S_i| ≦ 100 (1 ≦ i ≦ N, |S_i| は、S_i の文字数です。)
4
ab
ba
bab
cbab
No EPS
Yes b
No EPS
Yes a
No EPS
Yes a
Yes ab
No EPS
No b
Yes ba
Yes bab
2
abab
baba
No EPS
No b
No ba
Yes bab
No EPS
No a
No ab
Yes aba