trie

[Hsue66]

/*#include using namespace std;

define ALPHA 5

define MAX 100

struct TrieNode { TrieNode *child[ALPHA]; bool terminal;

void init() {
    terminal = false;
    for (int i = 0; i < ALPHA; i++)
        child[i] = 0;
}

};

struct Trie { TrieNode node[MAX]; TrieNode *Root; int size;

TrieNode* alloc() {
    return &node[size++];
}

void init() {
    size = 0;
    Root = alloc();
    Root->init();
}

void insert(TrieNode *now, char *str) {
    if (*str == '\0') {
        now->terminal = true;
        return;
    }

    int idx = *str - 'a';
    TrieNode *next;
    next = now->child[idx];
    if (next == 0) { //없는 경우
        next = alloc();
        next->init();
        now->child[idx] = next;
    }
    insert(next, str+1);
}

TrieNode* find(TrieNode *now, char *str) {
    if (*str == '\0') 
        return now;
    int idx = *str - 'a';
    TrieNode *next;
    next = now->child[idx];
    if (next == 0)
        return 0;
    find(next, str + 1);
}

};

int main() { Trie trie; trie.init(); trie.insert(trie.Root, (char)"abc"); trie.insert(trie.Root, (char)"ac"); trie.insert(trie.Root, (char*)"aba");

cout << "aba :";
if (trie.find(trie.Root, (char*)"aba"))
    cout << "YES" << endl;
else
    cout << "NO" << endl;

cout << "ad :";
if (trie.find(trie.Root, (char*)"ad"))
    cout << "YES" << endl;
else
    cout << "NO" << endl;

} */