問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
この問題ではトライ木に記録された文字列のうち、与えられた文字列 T をプレフィックスとして持つ文字列の数を返すメンバ関数 count_prefix(word: string): int
を作成してください。
N 個の文字列 S_1, ..., S_N が与えられます。
次に以下の Q 個のクエリに答えてください。
・文字列 T が与えられます。T をプレフィックスの1つとして持つ単語は S_1, ..., S_N の中に何個あるかを出力してください。
ある文字列のプレフィックスとは、その文字列の先頭から始まる連続部分文字列のことを指します。
例えば、文字列 "apple" のプレフィックスは"", "a", "ap", "app", "appl", "apple"の 6 つです。
N Q
S_1
...
S_N
query_1
...
query_Q
T
i 行目には i 番目のクエリに対する出力を行ってください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします
・1 ≦ N, Q ≦ 10^3
・S_i, T はアルファベット小文字で構成された文字列
・1 ≦ |S_i|, |T| ≦ 10^3 (|S_i|は、Sの文字数です。)
4 5
long
longlong
longest
leading
lo
long
longest
longlonglong
along
3
3
1
0
0
3 2
aaaa
aaaa
aaaa
a
aaaa
3
3