Untitled
unknown
plain_text
a year ago
1.2 kB
3
Indexable
#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); }
Editor is loading...