問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
これまでの問題ではパターン (表れるかを判定したい文字列) が1つの場合の PMA の構築を行いました。
この PMA を用いることでパターンマッチングがおこなえるようになります。
パターンを "abab", テキスト (パターンが表れるかを判定したい文字列)を "abaabab" とした場合を例に説明します。
まず、PMA は次の図のようになります。図中の、ラベルとして文字が振られている黒い辺はトライ木の構築時にできた辺 (文字に対する遷移)、青い辺は failure
で、赤い頂点は「パターンを受理する」頂点でした。
パターンマッチングの際にはテキストを 1 文字ずつ読み込み PMA の頂点を遷移していきます。 このときの動作を簡単に説明すると 次の (1), (2) の動作を 1 文字読み込む度におこなうことになります。
(1) 今いる頂点に読み込んだ文字の遷移が定義されていないなら、failure
を用いてその文字での遷移が定義されている頂点まで遷移する
(2) 今いる頂点には読み込んだ文字での遷移が定義されているでそれを使って遷移する
failure
による遷移をおこなった結果、照合箇所の左端が右方向に進み照合中の文字列が短くなっています。これが性質 (b) に対応するもので、PMA
構築時の failure
の「今の頂点の文字列の接尾辞に向かって引く」という引き方によるものです。AhoCorasick
クラスに次のようなメンバ関数 match(text: string): bool
を追加してください。 text
に対して PMA
を用いたマッチングを実行し、text
にパターンが含まれるならば true
、含まれないならば false
を返します。match(string text)
は次のような処理をおこないます。各変数の説明
・text の何文字目を見ているかを示す変数 i=1 とする.
・text の長さは L (0 < L) で, そのi文字目を text[i] とする.
・今いる頂点を表す変数 ptr の初期値を root とする.
実際の動作
while i ≦ Lの間
while ptrからtext[i]の文字を持つ辺が伸びていないとき
ptr = ptrからfailureで移動した先の頂点に更新
ptrをptrからtext[i]の文字を持つ辺で移動した頂点に更新
if ptrのis_patternがtrue
trueを返す
i = i+1とする
falseを返す
Yes
、含まれないならば No
を出力してください。
S
N
T_1
...
T_N
i 行目には T_i に対して S が含まれるかの判定結果を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて, 以下の条件をみたします
・1 ≦ N ≦ 100
・S, T_i (1 ≦ i ≦ N) は英小文字で構成される
・1 ≦ |S|, |T_i| ≦ 200 (1 ≦ i ≦ N, |S| は、S の文字数です。)
abab
3
abaabab
abcd
ababab
Yes
No
Yes
abc
4
abcdef
aaabc
ababcd
aaaaccc
Yes
Yes
Yes
No
aaaa
3
aaa
bbbb
aaaaa
No
No
Yes