PMAの構築 3 (パターンマッチング) (paizaランク A 相当)

作成した 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を返す

上の処理を用いた時の計算量について考えます。
テキストの長さを L とすると、文字による遷移の回数は最大でも L 回となります。
また、failure では必ず今いる頂点より浅い (根に近い)　頂点へと遷移することになります。
このことから、 failure での遷移は文字による遷移の回数よりも多くは行われず、最大でも L 回となります。
つまり、文字と failure 両方の遷移回数を合わせても 2L 回となるため、
PMA を用いてパターンマッチングを行ったときの計算量は O(L) となります。

最後に failure の意味について説明します。
ある頂点 u から出る failure は、「u が対応する文字列 S の、 S を除く接尾辞の中で、グラフ内に存在する最長の文字列 T の対応する頂点」へと引かれました。
実は AhoCorasick 法は問題「トライ木を用いたパターン検出」でおこなったトライ木による文字列検索を高速化したものと捉えられ、failure はその高速化を担います。
パターンとして "abcx", "bcdx", "cdef" が格納された次のようなトライ木を考えます。



このトライ木に failure を追加すると次の図のようになります。(根へと向かう failure は省略しています。)



さて、元のトライ木において T = "abcdef" というテキストに対するパターンマッチングを行う場合、テキストの i (1 ≦ i ≦ |T|) 文字目から始まる文字列 "abcdef", "bcdef", "cdef", "def", "ef", "f" それぞれの接頭辞にパターンが含まれるかを判定していました。
このとき、1 文字目からの文字列 "abcdef" を判定する場合は頂点 abc まで、2 文字目からの文字列 "bcdef" を判定する場合は頂点 bcd まで進み、この段階での遷移過程はそれぞれ 根 → a → ab → abc, 根 → b → bc → bcd となります。トライ木の頂点の文字列は現在照合中の文字列を表します。
上の手順において T の 1~3 文字目の "abc"を照合した後で再び 2 文字目から照合するのはあまり効率が良くなさそうです。そのため、"abc" から先頭の 1 文字を照合範囲から外し現在照合中の文字列を "bc" とすることを考えます。この処理をトライ木に適用することを考えると、それが abc から bc への failure です。failure を使うことで abc まで進んだ後に 根 → b → bc という遷移をせずに、直接 abc から bc に遷移できるようになります。他の頂点間での failure も同様で、これらが高速化に役立ちます。


入力としてパターンとする N 個の文字列 S_1, ..., S_N が与えられます。
最初に S_1, ..., S_N を格納した PMA を構築してください。
次に文字列 T が与えられます。
S_1, ..., S_N のうち 1 つ以上の文字列が、連続部分文字列として T に含まれるなら Yes, 含まれないなら No を出力してください。