Problem C HDU - 5687(字典树的三种操作)
程序员文章站
2022-04-17 21:29:18
...
题意:有三种操作,第一种是插入一个单词,第二种是删除具有这个前缀的所有单词,第三种是查询是否具有这个前缀的单词
题解:使用字典树,挑战最大的是删除这个操作,可以这样,如果没有这个前缀直接退出,如果有这个前缀,那么先将这个前缀之后所有的都消去,再回上来删除具有这个前缀的数量(很重要),直接看代码。
附上代码:
#include<bits/stdc++.h>
using namespace std;
const int maxnode=3e6+50;
const int sigma_size=26;
struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
void clear(){
sz=1;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
}
int idx(char c){
return c-'a';
}
void insert(string s){
int u=0,n=s.size();
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
ch[u][c]=sz++;
}
u=ch[u][c];
val[u]++;
}
}
void find_prefixes(string s,int len,bool &flag){
int u=0;
for(int i=0;i<len;i++){
if(s[i]=='\0'){
break;
}
int c=idx(s[i]);
if(!ch[u][c]){
flag=false;
return ;
}
u=ch[u][c];
}
if(val[u]){
return ;
}else{
flag=false;
return ;
}
}
void dfs(int u){
bool flag=false;
for(int i=0;i<26;i++){
if(val[ch[u][i]]){
val[ch[u][i]]=0;
dfs(ch[u][i]);
flag=true;
}
}
if(!flag){
return ;
}
}
void deletee(string s){
int u=0,len=s.size();
for(int i=0;i<len;i++){
if(s[i]==0){
break;
}
int c=idx(s[i]);
if(!ch[u][c]){
return ;
}
u=ch[u][c];
}
dfs(u);
int temp=val[u];
u=0;
for(int i=0;i<len;i++){
if(s[i]==0){
break;
}
int c=idx(s[i]);
u=ch[u][c];
val[u]-=temp;
}
}
};
Trie trie;
int n;
int main()
{
cin>>n;
string s1,s2;
trie.clear();
for(int i=0;i<n;i++){
cin>>s1>>s2;
if(s1[0]=='i'){
trie.insert(s2);
}else if(s1[0]=='d'){
trie.deletee(s2);
}else{
bool flag=true;
trie.find_prefixes(s2,s2.size(),flag);
if(flag){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
}
return 0;
}
上一篇: 烧香