Input Candidates

Time Limit : 1 sec, Memory Limit : 65536 KB

入力候補

携帯電話には、メールなどの文章を効率良く入力するために入力候補を表示する機能が搭載されています。これは、使われる頻度が高い単語を記録しておき、入力された文字を頭文字に持つ単語を入力候補として提示するものです。例えば、普段”computer”という単語を多く入力しているなら、”c”と入力するだけで候補として”computer”が提示されます。このような機能を自作するために、その基本部分として、記録されている文章の中から、指定された文字を頭文字に持つ単語を出現回数が多い順に出力するプログラムを作成しましょう。

文章、文字k(半角英字)を入力とし、その文字kを頭文字に持つ単語を出現数の順に出力するプログラムを作成してください。ただし、記録された文章は半角英小文字と半角空白からなり、複数の行で与えられます。1行の文字数は1文字以上1024文字以下とします。空白によって区切られる単語は1文字以上の20文字以下です。出現数が同じ単語が複数ある場合は、辞書式順序で出力します。出力する単語は最大5つまでとします。該当する単語が存在しない場合は”NA”と出力してください。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつで表されます。各データセットは以下のとおりです。

1行目 文章の行数n
2行目 1行目の文章(半角英小文字及び半角空白の列)
...
n+1行目 n行目の文章(半角英小文字及び半角空白の列)
n+2行目 頭文字k (半角英字)

出力

入力データセットごとに、指定された文字を頭文字にもつ単語または”NA”と出力します。

入力例

1
ben likes bananas the best among many fruits because bananas are sweet and cheap
b
1
winners get to visit aizu and the university of aizu and make many friends as well
a
3
ask alex about
the answer for the
assignment on android apps
a
2
programming is both
a sport and an intellectual puzzle
c
0

出力例

bananas because ben best
aizu and as
about alex android answer apps
NA

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/