Acwing 1927 自动补全（知识点：hash,二分，排序）

• 2022 年 6 月 12 日
• 筆記
• AcWing 刷题记录

读完题目第一想法是trie树 ，不过好像没怎么做过trie树的题，看y总给的知识点是二分排序，所以就有了如下思路；
但是但是，看完其他题解之后才坚定了我的想法，原来真的是这样排序，暴力啊！

具体步骤

• 最终要输出在字典中的位置，所以首先建立hash表存储位置；
• 开一个数组str进行排序（当然其他大佬用的vector当然更加直观，我不怎么用vector。。。）
• 对于给定前缀 pre，用二分找到字典序大于等于它的最左位置 p，p 之前的单词前缀一定不是 pre ；
• 之后判断p后面K-1个单词前缀是否一致;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int w,n;
unordered_map<string,int>mp;
string str[30010];
int main(){
	cin>>w>>n;
	for(int i=1;i<=w;i++)
	{
		string s="";
		cin>>s;
		mp[s]=i;
		str[i]=s;
	}
	sort(str+1,str+1+w);
	for(int i=1;i<=w;i++)
	cout<<str[i]<<" ";
	puts("");
	while(n--){
		int a;
		string pre;
		cin>>a>>pre;
		int p = lower_bound(str+1,str+1+w,pre)-str;
		//cout<<p<<" 最左边"<<endl;
		p = p + a -1;
		//cout<<p<<" 最后一个"<<endl;
		if(p < w && str[p].substr(0,pre.size()) == pre)
		cout<<mp[str[p]]<<endl;
		else 
		cout<<"-1"<<endl;
	}
	return 0;
}