现在有个字典要支持一下操作
1、insert : 往神奇字典中插入一个单词
2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串
字典树每个节点维护 sum[ i ]
delete 操作: 先查询包含该串的串个数 V, 该串的路径 每个点 - = V,
然后 memset(ch[u] ,0 ,sizeof (ch[u] ) )
#include<iostream> #include <algorithm> #include <cstring> using namespace std; const int N=5e5+4; char word[80]; int len,sum[N]; int ch[N][30],tot=1; int find(char *s){ int i,u=1; len=strlen(s); for(i=0;i<len;i++){ int c=s[i]-'a'; if(ch[u][c]==0){ return 0; } u=ch[u][c]; } return sum[u]; } void insert(char *s){ int i,u=1; len=strlen(s); for(i=0;i<len;i++){ int c=s[i]-'a'; if(ch[u][c]==0){ ch[u][c]=++tot; } u=ch[u][c]; sum[u]++; } } void del(char *s,int v){ int i,u=1; len=strlen(s); for(i=0;i<len;i++){ int c=s[i]-'a'; if(ch[u][c]==0){ return; } sum[u]-=v; u=ch[u][c]; } sum[u]=0; memset(ch[u],0,sizeof ch[u]); } int main(){ int t; scanf("%d",&t); while(t--){ char op[10]; scanf("%s%s",op,word); if(op[0]=='i') insert(word); else if(op[0]=='d') del(word,find(word)); else{ if(find(word)) printf("Yes\n"); else printf("No\n"); } } return 0; }
标签:HDU,ch,int,神奇,字符串,Problem,include,5687,字典 From: https://www.cnblogs.com/towboa/p/17157134.html