Trie 자료구조

백준 문제를 풀면서 알게된 Trie 자료구조에 대한 정리

 

많은 문자열중에서 같은 문자열을 찾을 때 최대길이가 m이라면 n번 시행할때 O(mn)으로 찾을 수 있고,

 

트라이를 만들 때도 O(mn)으로 만들 수 있게 한다.

 

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>

using namespace std;

struct Trie {
	char c;
	bool end;
	Trie* next[10];

	Trie() {
		end = false;
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; i++) {
			if (next[i]) delete next[i];
		}
	}

	void insert(string s) {
		if (s.size() == 0) {
			end = true;
		} else {
			if (next[s[0] - '0'] == NULL) {
				next[s[0] - '0'] = new Trie();
			}
			next[s[0] - '0']->insert(s.substr(1));
		}
	}
	bool isValid(string s) {
		if (s.size() == 0) return true;
		if (end) return false;
		return next[s[0] - '0']->isValid(s.substr(1));
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		Trie* T = new Trie();
		string s[10001];
		
		for (int i = 0; i < n; i++) {
			cin >> s[i];
			T->insert(s[i]);
		}
		bool isValid = true;
		for (int i = 0; i < n; i++) {
			if (!T->isValid(s[i])) isValid = false;
		}
		if (isValid) cout << "YES\n";
		else cout << "NO\n";
	}
}

https://www.acmicpc.net/problem/5052