問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
この問題ではデータ構造の 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にする
is_end
を true
にします。 is_end
を true
にします。これが "aa", "ab" を格納したトライ木となります。 Trie
のメンバ関数 search(word: string): bool
も必要となります。 word
がトライ木に格納されているかを確認する関数です。 Yes
、されていないなら No
を出力してください。
N M
S_1
...
S_N
T_1
...
T_M
i 行目には T_i がトライ木に格納されているかの判定結果を 1 行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて, 以下の条件をみたします
・1 ≦ N, M ≦ 100
・S_i (1 ≦ i ≦ N) , T_i (1 ≦ i ≦ M) は英小文字のみで構成される
・1 ≦ |S_i|, |T_j| ≦ 1000 (1 ≦ i ≦ N, |S_i| は、S_i の文字数です。)
5 3
ab
abcd
bc
bab
d
ab
abc
abcde
Yes
No
No
2 2
aaa
bbb
aabbccddee
cccc
No
No