Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.2 kB
1
Indexable
Never
#define MAXN 600006
 
struct trie {
    trie* child[26];
    int count;
}T[MAXN];
 
int node;
trie* root;
 
trie* getNode() {
    trie* p = &T[node++];
    p->count = 0;
    for (int i = 0; i < 26; i++) {
        p->child[i] = nullptr;
    }
    return p;
}
 
int searching(trie* p, char* str, bool del = false) {
    while (char ch = *str++) {
        if (ch == '?') {
            int sum = 0;
            for (int i = 0; i < 26; i++) {
                if (p->child[i])
                    sum += searching(p->child[i], str, del);
            }
            return sum;
        }
        else if (!p->child[ch - 'a'])
            return 0;
        p = p->child[ch - 'a'];
    }
    int res = p->count;
    if (del) p->count = 0;
    return res;
}
 
void init() {
    node = 0;
    root = getNode();
}
 
int add(char str[]) {
    trie* p = root;
    while (char ch = *str++) {
        if (!p->child[ch - 'a'])
            p->child[ch - 'a'] = getNode();
 
        p = p->child[ch - 'a'];
    }
    return ++p->count;
}
 
int remove(char str[]) {
    return searching(root, str, true);
}
 
int search(char str[]) {
    return searching(root, str);
}