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;
}