#include <memory>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <fstream>

struct Node {
	Node() : children(256) {}
	std::vector<std::unique_ptr<Node>> children;
	std::vector<std::string> words;
	Node* failNode;
};

size_t getPosFromChar(char ch)
{
	return ch < 0 ? 256 + ch : ch;
}

void addWordToTree(Node* currentNode, std::string word)
{
	std::for_each(word.begin(), word.end(), [&currentNode](auto ch) {
		auto pos = getPosFromChar(ch);
		if (currentNode->children[pos] == nullptr)
		{
			currentNode->children[pos] = std::make_unique<Node>();
		}

		currentNode = currentNode->children[pos].get();
	});

	currentNode->words.push_back(word);
}

void assignFailNode(Node* root, Node* node, size_t pos)
{
	auto currentNode = node;

	while (root != currentNode)
	{
		currentNode = currentNode->failNode;
		if (nullptr != currentNode->children[pos])
		{
			(*node->children[pos]).failNode = currentNode->children[pos].get();
			currentNode = root;
		}
	}

	if ((*node->children[pos]).failNode == nullptr)
	{
		node->failNode = root;
	}

	auto child = node->children[pos].get();
	child->words.insert(child->words.end(),
						child->failNode->words.cbegin(),
						child->failNode->words.cend());
}

void linkFailNodes(Node* root)
{
	root->failNode = root;

	std::queue<Node*> q;
	for (auto& child : root->children)
	{
		if (nullptr != child)
		{
			(*child).failNode = root;
			q.push(child.get());
		}
	}

	while (!q.empty())
	{
		auto currentNode = q.front();
		q.pop();

		for (auto i = 0; i < 256; ++i)
		{
			if (nullptr != currentNode->children[i])
			{
				assignFailNode(root, currentNode, i);
				q.push(currentNode->children[i].get());
			}
		}
	}
}

std::unordered_map<std::string, size_t> processText(Node *root, std::string text)
{
	std::unordered_map<std::string, size_t> wordFrequence;
	auto currentNode = root;

	std::for_each(text.cbegin(), text.cend(), [&currentNode, &wordFrequence, &root](auto ch) {
		auto pos = getPosFromChar(ch);

		while (nullptr == currentNode->children[pos] && currentNode != root)
		{
			currentNode = currentNode->failNode;
		}

		if(nullptr != currentNode->children[pos])
		{
			currentNode = currentNode->children[pos].get();

			std::for_each(currentNode->words.cbegin(), currentNode->words.cend(), [&wordFrequence](auto& word) {
				wordFrequence[word] ++;
			});
		}
	});

	return wordFrequence;
}

int main()
{
	auto root = std::make_unique<Node>();

	std::ifstream fin("ahocorasick.in");
	std::ofstream fout("ahocorasick.out");

	std::string text;
	std::getline(fin, text);

	auto dictionarySize = 0UL;
	fin >> dictionarySize;

	std::string word;
	std::vector<std::string> words;
	std::getline(fin, word); //extra

	while (std::getline(fin, word))
	{
		addWordToTree(root.get(), word);
		words.push_back(word);
	}

	linkFailNodes(root.get());

	auto wordFrequence = processText(root.get(), text);

	for (auto it = words.cbegin(); it != words.cend(); ++it)
	{
		fout << wordFrequence[*it] << '\n';
	}

    return 0;
}