3.0 KiB
百度、谷歌等搜索引擎，以及输入法等各种软件通常包含这样一个功能，当用户在输入框输入信息时，软件会提供一种“智能提示”。对用户所输入的信息，自动补全、列出可能的完整单词，提示给用户，以方便用户输入，提升用户体验。
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