-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathTrie.cpp
More file actions
106 lines (81 loc) · 1.98 KB
/
Trie.cpp
File metadata and controls
106 lines (81 loc) · 1.98 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <string>
#define N_ALPHABATS 26
using namespace std;
class TrieNode {
public:
TrieNode* child[N_ALPHABATS];
bool isTerm;
TrieNode() {
isTerm = false;
for (int i = 0; i < N_ALPHABATS; i++) {
child[i] = NULL;
}
}
~TrieNode() {
for (int i = 0; i < N_ALPHABATS; i++) {
if (child[i] != NULL) {
delete child[i];
}
}
}
int toNum(char c) {
return tolower(c) - 'a';
}
void insert(const char* words) {
if (*words == '\0') {
isTerm = true;
return;
}
int next = toNum(*words);
if (child[next] == NULL) {
child[next] = new TrieNode;
}
child[next]->insert(words + 1);
}
bool find(const char* words) {
if (*words == '\0') {
return isTerm;
}
int next = toNum(*words);
if (child[next] == NULL) {
return false;
}
return child[next]->find(words + 1);
}
};
int main(void) {
TrieNode root;
string words[5];
words[0] = "ABC";
words[1] = "ABCDE";
words[2] = "IJK";
words[3] = "IJKL";
words[4] = "IJKLM";
for (int i = 0; i < 5; i++) {
root.insert(words[i].c_str());
}
for (int i = 0; i < 5; i++) {
if (root.find(words[i].c_str())) {
cout << words[i] << "가 존재합니다." << endl;
}
else {
cout << words[i] << "가 존재하지 않습니다." << endl;
}
}
string Xwords[5];
Xwords[0] = "ABSTRACT";
Xwords[1] = "GOOD";
Xwords[2] = "NICE";
Xwords[3] = "YUNBIN";
Xwords[4] = "NAME";
for (int i = 0; i < 5; i++) {
if (root.find(Xwords[i].c_str())) {
cout << Xwords[i] << "가 존재합니다." << endl;
}
else {
cout << Xwords[i] << "가 존재하지 않습니다." << endl;
}
}
return 0;
}