#include
#include<unordered_map>
using namespace std;
class TrieNode
{
public:
unordered_map<char,TrieNode *> children;
string word;
};
class Trie
{
public:
TrieNode *root;
char endsymbol;
Trie()
{

this->root=new TrieNode();
	this->endsymbol='*';
	}
void insert(string str)
{
	TrieNode *current=this->root;
	for(int j=0;j<str.length();j++)
	{
		char letter=str[j];
		if(current->children.find(letter)==current->children.end())
		{
			TrieNode *newnode= new TrieNode();
			current->children.insert({letter,newnode});
		}
		current=current->children[j];
	}
	current->children.insert({this->endsymbol,nullptr});
	current->word=str;
}

};
void findString(int i,string bigString,unordered_map<string,bool> *contains,Trie *t);
vector multiStringSearch(string bigString, vector smallStrings) {
// Write your code here.
Trie *t = new Trie();
vector res;
for(string str:smallStrings)
{
t->insert(str);
}
unordered_map<string,bool> contains;
for(int i=0;i<bigString.length();i++)
{
findString(i,bigString,&contains,t);
}
for(string st:smallStrings)
{
res.push_back(contains.find(st)!=contains.end());
}

return res;
}
void findString(int i,string bigString,unordered_map<string,bool> *contains,Trie *f)
{
TrieNode *curr=f->root;
for(int j=i;j<bigString.length();j++)
{
//char letter=bigString[j];
if(curr->children.find(bigString[j])==curr->children.end())
{
break;
}

	curr=curr->children[bigString[j]];

if(curr->children.find(f->endsymbol)!=curr->children.end())
{
	contains->insert({curr->word,true});
}
}

}