void CSuffixTree::Print(std::ostream& os, char nullchar) const
{
	std::vector<CNode*> nodes;
	std::vector<CEdge*> edges;
	std::vector<std::pair<CNode*, CNode*> > suffix_links;

	CNode* root = pseudo_edge->head->edges[0]->head;
	CEdge* joker = root->link;
	root->link = 0; // не выводить джокер

	DFS(root, nodes, edges, suffix_links);

	root->link = joker; // вернуть джокер

	os << "digraph {" << std::endl;
	os << "\tnode" << nodes[0] << " [ shape = doublecircle ]" << std::endl;
	for(size_t i = 1; i < nodes.size(); ++i) {
		os << "\tnode" << nodes[i] << " [ shape = " << (nodes[i]->edges.empty() ? "box" : "ellipse") << ", fontsize = 10 ]" << std::endl;
	}
	std::string str = string;
	str[string.length() - 1] = nullchar;
	for(size_t i = 0; i < edges.size(); ++i) {
		os << "\tnode" << edges[i]->tail << " -> node" << edges[i]->head << " [ label = \"";
		for(size_t j = edges[i]->start; j < std::min(edges[i]->end, str.length()); ++j) {
			if(str[j] == '"' || str[j] == '\\') {
				os << '\\';
			}
			os << str[j];
		}
		os << "\", fontsize = 10, size = \"5.0,8.0\" ]" << std::endl;
	}
	for(size_t i = 0; i < suffix_links.size(); ++i) {
		os << "\tnode" << suffix_links[i].first << " -> node" << suffix_links[i].second << " [ style = \"dashed\" ]" << std::endl;
	}
	os << "}";
}

void CSuffixTree::DFS(CSuffixTree::CNode* node, std::vector<CSuffixTree::CNode*>& nodes, std::vector<CSuffixTree::CEdge*>& edges, std::vector<std::pair<CSuffixTree::CNode*, CSuffixTree::CNode*> >& suffix_links) const
{
	nodes.push_back(node);

	if(node->link != 0) {
		suffix_links.push_back(std::make_pair(node, node->link->head));
	}

	for(std::map<char, CEdge*>::iterator it = node->edges.begin(); it != node->edges.end(); ++it) {
		edges.push_back(it->second);
		DFS(it->second->head, nodes, edges, suffix_links);
	}
}