問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
作成した PMA を用いてパターンマッチングをおこないます。
このときの手順はパターンが 1 つの場合と全く同じです。AhoCorasick
クラスに次のようなメンバ関数 match(string text)
を追加してください。
このメンバ関数はパターンが含まれるかを調べたい文字列 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を返す
failure
では必ず今いる頂点より浅い (根に近い) 頂点へと遷移することになります。failure
での遷移は文字による遷移の回数よりも多くは行われず、最大でも L 回となります。failure
両方の遷移回数を合わせても 2L 回となるため、failure
の意味について説明します。 failure
は、「u が対応する文字列 S の、 S を除く接尾辞の中で、グラフ内に存在する最長の文字列 T の対応する頂点」へと引かれました。failure
はその高速化を担います。 failure
を追加すると次の図のようになります。(根へと向かう failure
は省略しています。) failure
です。failure
を使うことで abc まで進んだ後に 根 → b → bc という遷移をせずに、直接 abc から bc に遷移できるようになります。他の頂点間での failure
も同様で、これらが高速化に役立ちます。Yes
, 含まれないなら No
を出力してください。
N
S_1
...
S_N
T
答えを 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて, 以下の条件をみたします
・1 ≦ N ≦ 500
・S_i (1 ≦ i ≦ N), T は英小文字で構成される。
・1 ≦ |S_i| ≦ 500 (1 ≦ i ≦ N, |S_i| は、S_i の文字数です。)
・1 ≦ |T| ≦ 10^6 (|T| は、T の文字数です。)
3
cde
xyz
stu
abcdef
Yes
2
aaa
bbb
aabbccddee
No
1
xxxxxxxxxxxxxxxx
xxxxxx
No