字典树——HDU 5687 problem c

其实这个题不是很难，字典树模板加一点。 注意，一个单词，如果有要删除的前缀，那光要去掉后面的，还要去掉前面的。 代码

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int maxn = 26; struct Trie { Trie *next[maxn]; int v; }; Trie *root; void createTrie(char *str) { int len=strlen(str); Trie *p=root,*q; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]==NULL) { q=new Trie; q->v=1; for(int j=0;j<maxn;j++) q->next[j]=NULL; p->next[id]=q; p=p->next[id]; } else { p->next[id]->v++; p=p->next[id]; } } } int findTrie(char *str,int gg) { int len=strlen(str); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]!=NULL&&p->next[id]>0) { p=p->next[id]; p->v=p->v-gg; } else return 0; } return p->v; } void r(Trie *p) { if(p==NULL) return ; for(int i=0;i<maxn;i++) if(p->next[i]!=NULL) r(p->next[i]); p->v=0; //root=NULL; return ; } void d(char *str) { int len=strlen(str); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]!=NULL) { p=p->next[id]; } else return ; } findTrie(str,p->v); r(p); } void release(Trie *p) { if(p==NULL) return ; for(int i=0;i<maxn;i++) if(p->next[i]!=NULL) release(p->next[i]); free(p); root=NULL; return ; } int main() { char s[20]; root=new Trie; root->v=0; for(int i=0;i<maxn;i++) root->next[i]=NULL; int n; scanf("%d",&n); while(n--) { char s1[100],s2[100]; scanf("%s %s",s1,s2); if(s1[0]=='i') { createTrie(s2); } else if(s1[0]=='d') { d(s2); } else if(s1[0]=='s') { int k=findTrie(s2,0); if(k>=1) printf("Yes\n"); else printf("No\n"); } } release(root); return 0; }