#1

struct TrieNode
{
struct TrieNode *children[26];
bool end;
};
struct TrieNode *getNode(void)
{
struct TrieNode *Node = new TrieNode;

``````Node->end = false;

for (int i = 0; i < 26; i++)
Node->children[i] = NULL;

return Node;
``````

}
void insert(struct TrieNode *root, string key)
{
struct TrieNode *crawl = root;

``````for (int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if (!crawl->children[index])
crawl->children[index] = getNode();

crawl = crawl->children[index];
}
crawl->end = true;
``````

}
bool search(struct TrieNode *root, string key)
{
struct TrieNode *crawl = root;

``````for (int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if (!crawl->children[index])
return false;

crawl = crawl->children[index];
}

return (crawl != NULL && crawl->end);
``````

}
bool compare(pair<int, int> a, pair<int, int> b)
{
if( a.first > b.first) return true;
else if( a.first < b.first) return false;
else{
if( a.second < b.second) return true;
else return false;
}
}
vector Solution::solve(string a, vector &b) {
struct TrieNode* root=getNode();
for(int i=0; i<a.size(); i++){
string temp;
while( i<a.size() and a[i] != ‘’) temp += a[i], i++;
insert(root,temp);
}
vector<pair<int, int> > v;
for(int i=0; i<b.size(); i++){
int ans = 0;
for(int j=0; j<b[i].size(); j++){
string temp;
while( j<b[i].size() and b[i][j]!= '
’) temp += b[i][j], j++;
if(search(root,temp)) ans++;
}
v.push_back({ans, i});
}
sort(v.begin(), v.end(), compare );
vector ans;
for(int i=0; i<v.size(); i++){
ans.push_back(v[i].second);
}
return ans;
}