Complete solution using Hashing. complexity: O(nlogn*q)


#1

vector Solution::solve(string A, vector &B) {

unordered_set<string> gw;
string t,re;
for(int i=0;i<A.length();++i)
{
    if(A[i]!='_')
       t+=A[i];
    else
    {
         gw.insert(t);
         t=re;
    }
    if(i==A.length()-1)
        gw.insert(t);
       
}
t=re;
int cnt=0;
multimap<int,int,greater<int> > mp;
for(int i=0;i<B.size();++i)
{
    string e=B[i];
    for(int j=0;j<e.length();++j)
    {
        if(e[j]!='_')
            t+=e[j];
       else
       {
       		if(gw.find(t)!=gw.end())
       		++cnt;
       		
       		t=re;
	   }
       	if(j==e.length()-1)
       	{
       		 if(gw.find(t)!=gw.end())
       		 ++cnt;
       		 
       		 t=re;
		}
        
    }
    mp.insert({cnt,i});
    cnt=0;
}
vector<int> v;
for(auto it=mp.begin();it!=mp.end();++it)
{
    v.push_back((*it).second);
}
return v;

}