67 lines
3.0 KiB
Markdown
67 lines
3.0 KiB
Markdown
百度、谷歌等搜索引擎，以及输入法等各种软件通常包含这样一个功能，当用户在输入框输入信息时，软件会提供一种“智能提示”。对用户所输入的信息，自动补全、列出可能的完整单词，提示给用户，以方便用户输入，提升用户体验。
|
||
|
||
pic.jpg
|
||
|
||
这个功能是如何实现的呢？一种典型的实现方式是，在系统后台维护一个字典，当用户输入字符时，在字典中查找以用户当前输入的字符串为前缀的全部单词，选取其中历史使用率最高的若干单词作为候选词，建议给用户。
|
||
|
||
请编写程序实现上述功能。
|
||
|
||
备注：这里约定一个字符串不能称为自己的前缀。若用户输入的字符串恰好是字典中的一个单词，则该单词不必向用户建议。
|
||
|
||
输入格式:
|
||
输入第一行为3个正整数n、m、k。n为字典中单词个数。m为用户查询数，即用户输入的单词个数。对于用户输入的每个字符串，程序需要返回字典中以该字符串为前缀的、历史使用频率最高的k个单词。接下来n行，表示字典信息，每行为1个整数和1个字符串，整数表示单词的历史使用频率，字符串表示单词，请注意，单词包含的每个字符为a-z的小写字母或0-9的数字，即数字也可能构成字典中的单词。字典内的单词并非按使用频率有序存放。接下来m行，表示用户的查询，每行为一个a-z的小写字母或0-9的数字组成的字符串，表示用户的查询。另外请注意，由于字典往往是在用户历史数据的基础上加工而得，所以字典中可能出现重复单词，若某个单词在字典中出现多次，则其历史使用频率以最高者为准。 (n ≤ 10000, m ≤ 20000, k ≤ 10, 每个单词长度不超过20，单词历史使用频率小于2
|
||
31
|
||
)
|
||
|
||
输出格式:
|
||
对于用户输入的每个字符串，按使用频率降序输出字典中以该字符串为前缀的、历史使用频率最高的k个单词，每个占1行。若多个单词历史使用频率相同，则字典序靠前的单词排名靠前。若单词中包含数字，则字典序以ACSII码判定，即0<1<2<…<9<a<b<c<…<z。若字典中满足输出条件的单词个数大于0小于k，则有多少就输出多少个。若字典中没有满足输出条件的单词，则输出“no suggestion”。针对用户每个查询所输出的信息，用空行间隔。
|
||
|
||
输入样例:
|
||
20 3 4
|
||
1827187200 the
|
||
1595609600 to
|
||
1107331800 that
|
||
401542500 this
|
||
334039800 they
|
||
282026500 their
|
||
250991700 them
|
||
196118888 these
|
||
150877900 than
|
||
144968100 time
|
||
125563600 then
|
||
109336600 two
|
||
196120000 there
|
||
87862100 those
|
||
79292500 through
|
||
75885600 the
|
||
71578000 think
|
||
67462300 2
|
||
65648600 tx356
|
||
57087700 though
|
||
th
|
||
xxx
|
||
the
|
||
输出样例:
|
||
the
|
||
that
|
||
this
|
||
they
|
||
|
||
no suggestion
|
||
|
||
they
|
||
their
|
||
them
|
||
there
|
||
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
800 ms
|
||
Memory Limit
|
||
64 MB
|
||
Stack size limit
|
||
8192 KB
|
||
C++ (g++)
|
||
|
||
No Submit Records |