トライ木の構築 (paizaランク B 相当)

この問題ではデータ構造の 1 つであるトライ木を作成してもらいます。
トライ木は文字列の集合を索引化し、高速な検索を可能にするデータ構造です。

次の図は 5 つの文字列 "ab", "abcd", "bc", "bab", "d" を格納したトライ木を表します。根 (図の最も左にある、文字の書かれていない頂点) からある文字列 S の表れる経路でたどり着く頂点を頂点 S と呼びます。例えば頂点 ab なら、図の中央上部にある "ab" が書かれた赤い頂点のことです。頂点が赤いことは後に説明するメンバ変数 is_end が true であることを意味します。




「トライ木に、ある文字列 S が格納されているか」を判定したいときには頂点 S が存在し、かつ、頂点 S が赤いことを確認すればよいです。ある頂点が存在するかの判定は根から S となる経路でたどり着ける頂点があるかをおこなえばよいです。
例えば、文字列 "ab" がトライ木に格納されているかを調べたいとします。このとき、根から 'a' という辺、'b' という辺で順に移動できる頂点があるため、頂点 ab は存在します。
また、この頂点は赤いことから "ab" はトライ木に格納されている文字列であることが分かります。
同様に "abc", "abcde" がトライ木に格納されているかを調べたいとします。
"abc" の場合、頂点 abc は存在しますが赤色ではないので "abc" はトライ木に格納されていません。また、"abcde" の場合は 頂点 abcde が存在しないため、この文字列はトライ木に格納されていないことが分かります。
このように、トライ木はある文字列 S が格納されているかを O(S の長さ) で判定することが出来ます。

最初に次のような Trie クラスとその内部クラス Node を作成してください。

Nodeクラス  //トライ木の各頂点を表すクラス
-----------------------------------
メンバ変数
child[ch]: chをキーとして、頂点を返す連想配列 //文字 ch をラベルとして持つ辺を通って進める頂点を表す
is_end: bool    //この頂点は格納されたキーの最後の頂点であるか(trueならそう)

Trieクラス  //トライ木全体を表すクラス
-----------------------------------
メンバ変数
root: Node  //トライ木の根を表す
-----------------------------------
メンバ関数
insert(word: string): void  //文字列 word をトライ木に格納する(後述)
search(word: string): bool  //文字列 word がトライ木に格納されているかを調べる(本問題で実装する)

次に Trie のメンバ関数 insert(word: string): void の動作について説明します。
これは引数とする文字列 word をトライ木に格納する関数です。

各変数の説明
・word の何文字目を見ているかを示す変数を i とし，初期値を i=1 とする.
・word の長さはL (0 < L)で, そのi文字目を word[i] とする.
・今いる頂点を表す変数 ptr の初期値を root とする.

実際の動作
while i ≦ L の間
    if ptr からword[i] の文字を持つ辺が伸びていない(word[i]で進める頂点が存在していない)
        新しく頂点を作り, ptr のメンバ変数 child[word[i]] がその頂点を指すようにする
    ptr = ptr.child[word[i]] とする(頂点を移動する)
    i = i+1 とする
ptr の is_end を trueにする

例として、トライ木に "aa", "ab" を順に格納することを考えます。
トライ木は次のように変化していきます。

(1) 最初にトライ木は根だけで構成されます。


(2) 次に "aa" を格納します。今は根にいます。1 文字目の 'a' がついた辺、及びその辺で進める頂点がないので新しく頂点 a と辺を作り、移動します。


(3) 今は頂点 a にいます。2 文字目の 'a' がついた辺、及びその辺で進める頂点がないので新しく頂点 aa と辺を作り、移動します。


(4) 今は頂点 aa にいます。今いる頂点は word である "aa" の対応する頂点であるため、is_end を true にします。


(5) 次に "ab" を格納します。今は根にいます。1 文字目の 'a' がついた辺とそれを使って進める頂点 a があるので新しく頂点を作る必要はありません。この辺を使って頂点 a に移動します。


(6) 今は頂点 a にいます。2 文字目の 'b' がついた辺、及びその辺で進める頂点がないので新しく頂点 ab と辺を作り、移動します。


(7) 今は頂点 ab にいます。今いる頂点は word である "ab" の対応する頂点であるため、is_end を true にします。これが "aa", "ab" を格納したトライ木となります。


また、Trie のメンバ関数 search(word: string): bool も必要となります。
これは引数とする文字列 word がトライ木に格納されているかを確認する関数です。
こちらは最初に述べた「トライ木に、ある文字列 S が格納されているか」の判定を参考にして実装してみてください。

N 個の文字列 S_1, ..., S_N が与えられます。これらの文字列を格納したトライ木を構築してください。
その後、M 個の文字列 T_1, ..., T_M が与えられます。
T_i (1 ≦ i ≦ M) がトライ木に格納されているなら Yes、されていないなら No を出力してください。