奶牛贝茜买了一个新手机，并十分喜欢用它发短信。
但是它的大蹄子在手机的小屏幕上打字时遇到了麻烦，它总是把单词拼错。
农夫约翰同意通过编写一个自动补全程序来帮助它，当它输入部分单词时，该应用程序可以给出补全建议。
自动补全程序可以访问一个包含 个单词的词典，每个单词由 范围内的小写字母组成，其中所有单词中的字母总数最多为 。
现在给定一个包含 个部分单词的列表，每个部分单词最多包含
对于每个部分单词 ，还会提供一个整数 ，自动补全程序需要找到词典中以部分单词 i 作为前缀的所有单词中，按字典序排序排在第
也就是说，对所有部分单词 i 的有效补全按字典序进行排序，输出此顺序下的第
输入格式 第一行包含两个整数 和 。
接下来
接下来 行，每行首先包含一个整数 ，然后包含一个部分单词 。
输出格式 共 行，第 行输出部分单词 的第 个有效补全在词典中出现的位置（一个
如果第 个有效补全不存在，则输出 ????1??。
数据范围
输入样例：
10 3dabbaabdaaaaaaaaababcacdadba4 a2 da4 da
输出样例：
31-1
样例解释???a??? 的自动补全为 ??aa,aaa,aab,ab,abc,ac???，第四个为 ??ab??，在词典中排第 3 个。
??da??? 的自动补全为 ??daa,dab,dadba???，第二个为 ??dab??，在词典中排第 1 个。
??da?? 不存在第四个自动补全。
排序 + 二分 + hash
#include<iostream>#include<algorithm>#include<unordered_map>using namespace std;const int N = 30010;int w, n;string str[N];unordered_map<string, int> mp;int get(string s){ int l = 0, r = w + 1; while(l < r){ int mid = l + r >> 1; if(str[mid] >= s) r = mid; else l = mid + 1; } return l;}int main(){ cin >> w >> n; for(int i = 1; i <= w; i++) cin >> str[i], mp[str[i]] = i; sort(str + 1, str + w + 1); while(n–){ int idx; string s; cin >> idx >> s; int p = get(s); if(p == 0 || p == w + 1 || p + idx – 1 > w) puts(“-1”); else{ string s2 = str[p + idx – 1]; if(s == s2.substr(0, s.size())){ cout << mp[str[p + idx – 1]] << endl; }else puts(“-1”); } } return 0;}
【本文转自：韩国服务器 kt.html提供,感谢支持】或许是某个未开发的荒凉小岛，或许是某座闻名遐迩的文化古城。
