[DS] trie 구현

문제 링크

11478 서로 다른 부분 문자열

해당 문제를 substr + set을 이용하여 중복을 제거함으로써 문제를 풀 수 있다. 다만 이 방식으로 문제를 풀 경우, 호출 횟수 및 시간복잡도가 substr(500500) + set(log(500500)) 이렇게 되기 때문에 꽤나 오래 걸리게 된다.

따라서 시간을 줄이기 위한 풀이로 trie를 구현하여 풀 수도 있다.

trie 구현 풀이

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct Trie {
	map<char, Trie*> trie;

	void insert(const char* p_s) {
		if (!*p_s) {
			return;
		}
		if (trie[*p_s] == nullptr) {
			trie[*p_s] = new Trie;
		}
		trie[*p_s]->insert(p_s + 1);
	}
};

int trie_node_cnt(Trie* root) {
	int cnt = root->trie.size();
	for (auto it : root->trie) {
		cnt += trie_node_cnt(it.second);
	}
	return cnt;
	}	

int main() {
	Trie trie_root;

	string s;
	cin >> s;

	for (int idx = 0; idx < s.size(); idx++) {
		trie_root.insert(s.substr(idx, s.size()).c_str());
	}

	cout << trie_node_cnt(&trie_root);

	return 0;
}

reference

https://melonicedlatte.com/algorithm/2018/08/12/230648.html