トライ木を用いたパターン検出 (paizaランク A 相当)

パターンとする N 個の文字列 S_1, ..., S_N とパターンが含まれているかを調べたい文字列 T が与えられます。
S_1, ..., S_N の中で少なくとも 1 つ以上の文字列が T の連続部分文字列として含まれるなら Yes 、含まれないなら No を出力してください。
この問題ではトライ木を用いて、|T| を T の長さ、max(S) を S_1, ..., S_N の最大の長さとしたとき、以下の方法で O(|T| × max(S)) で解くことができます。


ある文字列の接頭辞とは、その文字列の先頭から始まる連続部分文字列のことを指します。
例えば、文字列 "apple" の接頭辞は "" (長さ 0 の文字列), "a", "ap", "app", "appl", "apple"の 6 つです。
トライ木を使うことで T の接頭辞にトライ木に格納された文字列が存在するかを調べることが出来ます。そのため、 S_1, ..., S_N を格納したトライ木を作成し、 T の i 文字目からその最後の文字までの連続部分文字列 T{i:} の接頭辞がトライ木に格納されているかを調べるという処理を、i を 1 ~ |T| としておこなえばよいです。

入出力例 1 を用いて説明します。このとき、S_1, ..., S_N を格納したトライ木は次の図となります。赤い頂点は根からの経路がパターンとなる頂点であることを示します。



T = "abxstu" です。まず、T{1:} である "abxstu" の接頭辞にパターンが含まれているかを確認したいです。T{1:} をトライ木を用いて検索すると頂点 ab までは進めます。T{2:}, T{3:} に関しても赤い頂点に到達することはありません。T{4:} は "stu" です。この文字列はパターンそのもので、トライ木による検索では赤い頂点に到達することから答えは Yes となります。