Boj 14725) 개미굴

문제

백준 14725

설명

Suffix Array 와 비슷한 역할을 하는 자료구조 연습문제.

시간 복잡도

O(\(\mathrm{N}\mathrm{K}\mathrm{T}\))

코드

struct Node
{
	Node() {}
	Node(const string& id) : id(id){}
	string id;
	list<Node> childs;
};

Node root;
void Print(Node* cur, int depth)
{
	for (int i = 0; i < depth; i++) cout << "--";
	cout << cur->id << '\n';

	for (auto& child : cur->childs)
		Print(&child, depth + 1);
}

int StringComp(string& a, string& b)
{
	int min_size = min(a.size(), b.size());
	int prefix = -1;
	while (prefix + 1 < min_size && a[prefix + 1] == b[prefix + 1]) prefix++;
	if (prefix < 0) return a[0] < b[0];
	if (prefix + 1 == min_size)
	{
		if (prefix + 1 == a.size() && prefix + 1 == b.size()) return 2;
		return a.size() < b.size(); // 작은 쪽이 prefix 와 같으므로 먼저옴
	}
	return a[prefix + 1] < b[prefix + 1];
}

int main()
{
	fastio;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t; cin >> t;
		Node* cur = &root;
		auto iter = cur->childs.begin();
		while (t--)
		{
			int r = -1;
			string a; cin >> a;
			for (; iter != cur->childs.end(); iter++)
			{
				r = StringComp(a, iter->id);
				if (r == 2) break;
				if (r == 1) break;
			}
			if (r != 2) cur = &*cur->childs.insert(iter, a);
			else cur = &*iter;
			iter = cur->childs.begin();
		}
	}
	for(auto& child: root.childs)
		Print(&child, 0);
}