// Problem C.cpp #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define PI 3.1415926535897932626 #define EXIT exit(0); #define PAUSE system("pause"); #define DEBUG puts("Here is a BUG"); #define SYNC_CLOSE ios::sync_with_stdio(false); #define what_is(x) cout << #x << " is " << x << endl; #define CLEAR(name, init) memset(name, init, sizeof(name)); const double eps = 1e-8; const int MAXN = (int)1e5 + 5; using namespace std; struct Trie { int seq; bool isStr; Trie *next[26]; }; void insert(Trie *root, char const *s) { if(root == NULL || *s == '\0') return; Trie *p = root; while(*s) { if(p->next[*s-'a'] == NULL) { Trie *temp = (Trie *)malloc(sizeof(Trie)); memset(temp->next, 0, sizeof(temp->next)); temp->isStr = false; p->next[*s-'a'] = temp; p = temp; // putchar(*s); cout << temp->seq << ' '; } else p = p->next[*s-'a']; s++; } p->isStr = true; return; } bool search(Trie *root, const char *s) { Trie *p = root; while(NULL != p && *s) { p = p->next[*s-'a']; // cout << *s << "->" << p << endl; s++; } // if (p) printf("p->seq = %d\n", p->seq); return NULL != p; } void delet(Trie *root, const char *s) { const char *ss = s; Trie *p = root, *last = p, *pre = p; while(NULL != p && *s) { bool flag = false; for(int i = 0; i < 26; i++) { if (*s - 'a' == i) continue; if (NULL != p->next[i]) { flag = true; } } if (p->isStr) { flag = true; } if (flag) { // DEBUG; pre = p; last = p->next[*s-'a']; ss = s; // what_is(*ss); } p = p->next[*s-'a']; s++; } // if (p) printf("p->seq = %d\n", p->seq); if (NULL != p) { Trie *tmp = pre; // what_is(pre); // ss--; while(*ss) { Trie *net = tmp; tmp = tmp->next[*ss-'a']; // cout << *(ss) << " " << net->next[*ss-'a'] << endl; net->next[*ss-'a'] = NULL; ss++; } } } void del(Trie *root) { for(int i = 0; i < MAXN; i++) { if(root->next[i]) { del(root->next[i]); } } free(root); } char s[MAXN]; int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("D:\\Documents\\Disk_Synchronous\\Programs\\Acm\\input.txt", "r", stdin); #endif int n; while(cin >> n) { Trie *root = (Trie *)malloc(sizeof(Trie)); root->seq = 0; root->isStr = false; memset(root->next, 0, sizeof(root->next)); while(n--) { char ord[20]; scanf("%s%s", ord, s); if (ord[0] == 'i') { insert(root, s); } else if (ord[0] == 's') { if (search(root, s)) puts("Yes"); else puts("No"); } else { delet(root, s); } } // del(root); } return 0; }