Auto Complete problem

Cristian was developing an application. He was using in-built Auto Complete function, which was slow and taking more execution time than expected. So, he thought of taking help from you to write the fast Auto Complete function. He will give you a dictionary as argument, your task is to give suggestions for Auto Complete on every character is entered in Text field. In a dictionary all words will be distinct and if the word which is typed is available in dictionary then that word will also come in suggestion. For example if 'a' is typed and 'a' is present in dictionary, then it will come in suggestion.

P.S. - Suggestions will be in ascending order. Print 0 if no suggestions found.

Input:

First line represents T test case. Every test case contains 3 lines of input. First line of every test case represents number of words in dictionary. Second line of every test case represents words of dictionary. Third line of every test case represents the word to be searched in dictionary.

Output:

Print the suggestions for each word typed in new line in ascending order. Print 0 if no suggestions found.

Constraints:

1 ≤ T ≤ 100

1 ≤ Number of words in Dict ≤ 50

1 ≤ Length of every word of Dict ≤ 50

1 ≤ query length ≤ 50

example 1:

input:

4

abc ab a abcd

abcd

output:

a ab abc abcd 

ab abc abcd 

abc abcd 

abcd 

0

example 2:

input:

5

abc ab a abcd aba

abcd

output:

a ab aba abc abcd 

ab aba abc abcd 

abc abcd 

abcd 

0

c++ implementation:

#include <bits/stdc++.h> 
using namespace std; 
#define ll long long int
 

int main() 
{ 
    int t;
    cin>>t;
    while(t--){
        vector<string>v;
        ll n;
        cin>>n;
        for(int i=0;i<n;i++){
            string  c;
            cin>>c;
            v.push_back(c);
        }
        sort(v.begin(),v.end());
        //reverse(v.begin(),v.end());
        map<string,vector<string>>m;
        string s;
        cin>>s;
        string d = "";
        for(int i=0;i<v.size();i++){
            d = "";
            for(int j=0;j<v[i].size();j++){
                d+=v[i][j];
                m[d].push_back(v[i]);
            }
        }
        string f = "";
        for(int i=0;i<s.size();i++){
            f+=s[i];
            if(m[f].size()>0){
                for(int i=0;i<m[f].size();i++){
                    cout<<m[f][i]<<" ";
                }
                cout<<endl;
            }
        }
      cout<<0<<endl;
    }
    return 0;
}