Trie 연습

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>
#include <cassert>
#define MAXSTR 100

#define CMD_INSERT 100
#define CMD_SEARCH 200
#define CMD_COUNT 300
#define CMD_DELETE 400

extern void init_trie();
extern void Tries_insert(char key[MAXSTR + 1]);
extern bool Tries_search(char key[MAXSTR + 1]);
extern int Tries_CountofkeysWithPrefix(char key[MAXSTR + 1]);
extern void Tries_deleteKey(char key[MAXSTR + 1]);

static bool run() {
    bool isAccepted = true;

    int T;
    scanf("%d", &T);

    int cmd, val, answer;
    bool ret;
    char str[MAXSTR + 1];

    init_trie();
    while (T--)
    {
        scanf("%d %s", &cmd, str);
        switch (cmd)
        {
        case CMD_INSERT:
            Tries_insert(str);
            break;

        case CMD_SEARCH:
            ret = Tries_search(str);
            val = ret ? 1 : 0;
            scanf("%d", &answer);
            isAccepted &= (val == answer);
            break;

        case CMD_COUNT:
            val = Tries_CountofkeysWithPrefix(str);
            scanf("%d", &answer);
            isAccepted &= (val == answer);
            break;

        case CMD_DELETE:
            Tries_deleteKey(str);
            break;

        default:
            assert(false);
        }
    }

    return isAccepted;
}

int main()
{
    setbuf(stdout, NULL);
    freopen("input.txt", "r", stdin);

    int T;
    scanf("%d", &T);

    for (int tc = 1; tc <= T; ++tc)
    {
        if (run()) {
            printf("#%d 100\n", tc);
        }
        else {
            printf("#%d 0\n", tc);
        }
    }

    return 0;
}

---

#define MAX_N 10
#define MAXSTR 100

struct TRIE {
    int next[26];
    int prefix, end;
}trie[MAX_N * MAXSTR + 100];
int idx;

void init_trie() {
    for (int i = 0; i <= idx; i++) {
        for (int j = 0; j < 26; j++) trie[i].next[j] = 0;
        trie[i].prefix = trie[i].end = 0;
    }
    idx = 0;
}

void Tries_insert(char key[MAXSTR + 1]) {
    int cur = 0;
    for (int i = 0; key[i]; i++) {
        int next = key[i] - 'a';
        if (!trie[cur].next[next]) 
            trie[cur].next[next] = ++idx;
        cur = trie[cur].next[next];
        trie[cur].prefix++;
    }
    trie[cur].end++;
}
bool Tries_search(char key[MAXSTR + 1]) {
    int cur = 0;
    for (int i = 0; key[i]; i++) {
        int next = key[i] - 'a';
        if (!trie[cur].next[next]) return false;
        cur = trie[cur].next[next];
    }
    if (trie[cur].end) return true;
    return false;
}

int Tries_CountofkeysWithPrefix(char key[MAXSTR + 1]) {
    int cur = 0;
    for (int i = 0; key[i]; i++) {
        int next = key[i] - 'a';
        if (!trie[cur].next[next]) return 0;
        cur = trie[cur].next[next];
    }
    return trie[cur].prefix;
}

void Tries_deleteKey(char key[MAXSTR + 1]) {
    if (Tries_search(key)) {
        int cur = 0;
        for (int i = 0; key[i]; i++) {
            int next = key[i] - 'a';
            cur = trie[cur].next[next];
            trie[cur].prefix--;
        }
        trie[cur].end--;
    }
}

---

1
8
100 abc
100 xyz
100 abc
100 abcd
100 abcde
100 xyzp
200 abc
1
200 xyz
1