두찡의 일상

백준 문제를 풀면서 알게된 Trie 자료구조에 대한 정리 많은 문자열중에서 같은 문자열을 찾을 때 최대길이가 m이라면 n번 시행할때 O(mn)으로 찾을 수 있고, 트라이를 만들 때도 O(mn)으로 만들 수 있게 한다. #include #include #include #include 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)..