自动补全（春季每日一题 58）

自动补全（春季每日一题 58）

奶牛贝茜买了一个新手机，并十分喜欢用它发短信。

但是它的大蹄子在手机的小屏幕上打字时遇到了麻烦，它总是把单词拼错。

农夫约翰同意通过编写一个自动补全程序来帮助它，当它输入部分单词时，该应用程序可以给出补全建议。

输入样例：

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#include#includeusing namespace std;const int N = 30010;int w, n;string str[N];unordered_map 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。