트라이(Trie)

트라이의 개념은 쉽지만 글로 쓰긴 너무 길다.

 

<가장 기본 문제>

까먹었을 때 이문제만 한번 다시 풀어보면 기억 날 것.

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

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 4;
struct Trie {
	Trie* next[26];
	bool term;
	Trie() {
		term = false;
		for (int i = 0; i < 26; i++)
			next[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i]) delete next[i];
	}

	void insert(char* key) {
		if (*key == NULL) {
			term = true;
			return;
		}
		int c = *key - 'a';
		if (next[c] == NULL) next[c] = new Trie();
		next[c]->insert(key + 1);
	}
	bool find(char* key) {
		if (*key == NULL) return term;
		int c = *key - 'a';
		if (next[c] == NULL) return 0;
		return next[c]->find(key + 1);
	}
};

int main() {
	int n, m; cin >> n >> m;
	Trie* root = new Trie();
	for (int i = 0; i < n; i++) {
		char input[500]; cin >> input;
		root->insert(input);
	}
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		char input[500]; cin >> input;
		if (root->find(input)) cnt++;
	}
	cout << cnt << '\n';
}

 

<기본 코드>

const int ALPH = 26; //숫자 문자열이면 10
struct Trie {
	Trie* next[ALPH];
	bool term;
	Trie() {
		term = false;
		for (int i = 0; i < ALPH; i++)
			next[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < ALPH; i++)
			if (next[i]) delete next[i];
	}
    //재귀를 돌며 insert
	void insert(char* key) {
		if (*key == 0) {
			term = true;
			return;
		}
		int c = *key - '0';
		if (next[c] == NULL) next[c] = new Trie();
		next[c]->insert(key + 1);
	}
    //find함수. 이부분을 변형해서 푸는 문제가 많다. 역시 재귀로 구현
    Trie* find(const char* key) {
        if (*key == '\0') 
        	return this;//문자열이 끝나는 위치를 반환
        int curr = *key - '0';
        if (next[curr] == NULL) return NULL;//찾는 값이 존재하지 않음
        return next[curr]->find(key + 1); //다음 문자를 탐색
    }
};