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

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

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

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

	currentNode->words.push_back(index);
}

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 < 130; ++i)
		{
			if (nullptr != currentNode->children[i])
			{
				assignFailNode(root, currentNode, i);
				q.push(currentNode->children[i].get());
			}
		}
	}
}

void processText(Node *root, std::string text, size_t frequence[])
{
	auto currentNode = root;

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

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

			for(const auto& word : currentNode->words)
			{
			    ++frequence[word];
			}
		}
	}
}

size_t frequence[101];
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::getline(fin, word); //extra

	size_t index = 0UL;
	while (std::getline(fin, word))
	{
		addWordToTree(root.get(), word, index);
		++index;
	}

	linkFailNodes(root.get());

	processText(root.get(), text, frequence);

	for(size_t i=0; i<dictionarySize; ++i)
    {
        fout << frequence[i] << '\n';
    }

    return 0;
}