The first thought after reading the topic is trie Trees , But I haven't done much trie The question of trees , see y The total knowledge points given are binary sorting , So we have the following ideas ;
But but , After reading other solutions to the problems, I decided my mind , It turns out that the order is really like this , Violence ！
Specific steps
- The position of the final output in the dictionary , So first establish hash Table storage location ;
- Open an array str Sort （ Of course, other big guys use it vector Of course, it is more intuitive , I don't use much vector...）
- For a given prefix pre,
Use two points to find the leftmost position where the dictionary order is greater than or equal to p,p The previous word prefix must not be pre; - After judgment p Back K-1 Whether the prefixes of words are consistent ;
#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<<" Leftmost "<<endl;
p = p + a -1;
//cout<<p<<" the last one "<<endl;
if(p < w && str[p].substr(0,pre.size()) == pre)
cout<<mp[str[p]]<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}
Acwing 1927 Automatic completion （ Knowledge point ：hash, Two points , Sort ） More articles about
- bootstrap3-typeahead Automatic completion
A cool auto completion plug-in http://twitter.github.io/typeahead.js stay bootstrap Use in typeahead plug-in unit , Complete auto completion Related documents :https://gith ...
- vue In implementation , Automatic completion function
Knowledge point : utilize vue The basic syntax implementation of , Automatic completion function Reference blog :https://www.jb51.net/article/136282.htm effect : In the text box , Enter the relevant name , Call background interface , Fill the data in the drop-down ...
- jQuery The mailbox drop-down list is automatically completed
review I think you must have seen , When filling in an email on a website , Not finished yet , A series of drop-down lists will appear , Help you automatically complete the mailbox function . Now we use jQuery Let's do it . Blogger's original code , If the code is not perfect, I hope you have more ...
- eclipse Setting of automatic completion
eclipse Setting of automatic completion If you used Visual Studio After the automatic completion function of , Use it again eclipse Automatic completion function of , I believe you will be a little disappointed . however eclipse It's actually very powerful ,eclipse Of ...
- vim add to php Automatic completion And format the code
Automatic completion , modify /etc/vimrc Configuration of vim /etc/vimrc add to : filetype plugin on autocmd FileType php set omnifunc=phpcomp ...
- Eclipse Automatic completion setting
If you used Visual Studio After the automatic completion function of , Use it again eclipse Automatic completion function of , I believe you will be a little disappointed . however eclipse It's actually very powerful ,eclipse There is no automatic completion for VS So good because ecl ...
- Autocomplete Automatic completion （Webform Actual combat ）
Introductory words Because the project needs to use an automatic completion function , Function description : Need one : When adding new recipients , The automatic drop-down displays all the recipient information in the database ( The information displayed includes : full name - Mailing address - Contact information ) Demand two : Choose a time when it's worth it , To assign to ...
- eclipse Setting of automatic completion ( Automatic prompt )
If you used Visual Studio After the automatic completion function of , Use it again eclipse Automatic completion function of , I believe you will be a little disappointed . however eclipse It's actually very powerful ,eclipse There is no automatic completion for VS So good because e ...
- jQuery AutoComplete Automatic completion
jQuery.AutoComplete It's based on jQuery The automatic completion plug-in of . With the help of jQuery Excellent cross browser features , Compatible Chrome/IE/Firefox/Opera/Safari And so on . , ...
- Vim Automatic completion artifact –YouCompleteMe
One . brief introduction YouCompleteMe yes Vim The automatic completion plug-in of , Compared with similar plug-ins , It has the following advantages 1. Based on semantic completion 2. The integration implements a variety of plug-ins clang_complete.AutoComplPop .Super ...
Random recommendation
- Strategy oriented VI Design
Evaluate a sign from an aesthetic point of view (LOGO) Not the best way , The logo is not designed for beauty pageants . In addition to the aesthetic function, the logo shall also include many elements . To say the sign , First from CIS( Corporate image system ) Start with , It's divided into two parts MI.VI and BI, Refer to the enterprise's ...
- Atitit. Trojan virus forced shut down 360 360tray.exe Methods
Atitit. Trojan virus forced shut down 360 360tray.exe Methods 1. taskkill /im Process name 1 2. use wmic process where name=" Process name &qu ...
- tbb flow graph node types
- Record the form with poi Export of word
It is also the code found on the Internet http://53873039oycg.iteye.com/blog/2152009, But horizontal merging of cells did not succeed . Only a very stupid way to build a lot of table public void fillT ...
- Unity3D Script -- real 1
1. Unity3D Action script Unity3D Scripts are used to Unity3D Engine order announcement . JavaScript Global variables : stay Inspector You can see in , And its value can be changed . Other scripts can call this variable . C# public (pu ...
- say something final keyword ( There seems to be dry goods )
stay java Development process ,final Is a commonly used keyword , It's just used to decorate classes , Methods and variables , The table name class cannot be inherited , Method will not be overridden , Variables cannot be changed , Say it quietly ,private Methods are also implicit final. Through a period of time ...
- python The small white ( No programming foundation , No computer foundation ) The way of development , Auxiliary knowledge 6 python character string / Tuples / list / Dictionaries are interchangeable
Magical mutual transformation , Xiao Bai can have a look at , Very helpful #1. Dictionaries dict = {'name': 'Zara', 'age': 7, 'class': 'First'} # Dictionary to string , return :<type ...
- VS2015 Post FAQs
1. Precompile at release This is shown below : Problems encountered Use abp I quote System.Collections.Immutable.dll, But the project compilation keeps going wrong , screening : View project references , You can see System.Col ...
- .NET Core in IOptions What's the usage?
I just found that IOptions A use of —— Convenient in .NET Core Strong type configuration is used in applications . without IOptions, To use strong type configuration, you need to solve the following problems yourself 2 A question : 1) Set profile ( such as appsetting ...
- Learn from what you know | AI stay Facebook What role does it play in cleaning up harmful content ？
" Learn from what you know " It's a brand column created by Netease yunyidun , The words come from Chinese · Wang Chong < The theory of scale · Practical knowledge >. people , Ability is superior to inferior , Only by studying can we know the truth of things , Then there is wisdom , If you don't ask, you won't know ." Know things ...
