세번째 스터디 : Trie - gomamon/twitch_algorithm GitHub Wiki

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_CHA = 26;

struct Trie {
	Trie* children[MAX_CHA];    
	bool finish;   

	Trie() {
		fill(children, children+MAX_CHA, nullptr );
        finish = false;
	}
	~Trie() {
		for (int i = 0; i < MAX_CHA; i++)
			if (children[i])
				delete children[i];
	}

	void insert(const char* key) {
		if (key[0] == '\0')
			finish = true;    

		else {
			int next = key[0] - 'A';

			if (children[next] == NULL)
				children[next] = new Trie(); 
			children[next]->insert(key + 1);    
		}
	}
	Trie* find(const char* key) {
		if (*key == '\0')	return this;	

		int next = *key - 'A';
		if (children[next] == NULL)	return NULL;
		return children[next]->find(key + 1); 
	}
};

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_CHA = 10;

struct Trie {
	Trie* children[MAX_CHA];
	bool finish;

	Trie() {
		fill(children, children + MAX_CHA, nullptr);
		finish = false;
	}
	~Trie() {
		for (int i = 0; i < MAX_CHA; i++)
			if (children[i])
				delete children[i];
	}

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;

		else {
			int next = *key - '0';

			if (children[next] == NULL)
				children[next] = new Trie();
			children[next]->insert(key + 1);
		}
	}
	bool find(const char* key) {
		if (*key == '\0')	return false;
		if (finish) return true;

		int next = *key - '0';
		if (children[next] == NULL)	return NULL;
		return children[next]->find(key + 1);
	}
};


int main() {
	int t;
	scanf("%d", &t);

	while(t--){
		char te[10002][11];
		int n;
		bool rel = true;

		scanf("%d", &n);

		Trie* root = new Trie;

		for (int i = 0; i < n; i++) {
			scanf("%s",& te[i]);
			root->insert(te[i]);
		}
		for (int i = 0; i < n; i++) {
			if (root->find(te[i])) rel = false;
		}
		printf("%s\n", rel ? "YES" : "NO");

		delete root;
	}
}