Trie树练习

· · 个人记录

T1
一道字典树的模板。
字典树（又称Trie树）是一个树形结构，可以快速插入 、删除字符串以及匹配前缀。
简单地说，就是有一个多叉树，每个结点都有自己的编号，每条有父结点连接到子结点的边上都有一个字符。

若要插入字符串，则从根结点开始遍历每一条边。若有符合的字符，则沿这条边继续往下遍历，处理字符串的下一位；否则，为这个结点添加一个子节点，编号为当前树中最大编号+1，再沿这条边继续往下遍历，处理字符串的下一位。记得要将前缀数组中的值+1。

若要查找字符串，也从根结点开始遍历每一条边。若有符合的字符，则沿这条边继续往下遍历，处理字符串的下一位；否则，直接判为查找失败。
如果最后找到了整个字符串（即使没有遍历到树叶），则返回这个结点在前缀数组中的值（再遍历太费时间了，这就是字典树的优势）。

若要删除字符串，还是根结点开始遍历每一条边。若有符合的字符，则将当前结点前缀数组的值减去这个字符串的前缀数组的值（这是为了预防在下次查找中错误的被查找到），若前缀数组的值 \le 0 ，则将这个结点删除。

详见Code:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int n;
string s1,s2;
int trie[400001][26];
int tot, sum[400001];
char s[31];
void ist(){
    int ls=strlen(s);
    int root=0;
    for(int i=0;i<ls;i++){
        int id=s[i]-'a';
        if(!trie[root][id]){
            ++tot;
            trie[root][id]=tot;
        }
        ++sum[trie[root][id]];
        root=trie[root][id];
    }
    return; 
}
int src(){
    int root=0;
    int ls=strlen(s);
    for(int i=0;i<ls;i++){
        int id=s[i]-'a';
        if(!trie[root][id]) return 0;
        root=trie[root][id];
    }
    return sum[root];
}
void del(){
    int ls=strlen(s),k=src();
    int root=0;
    for(int i=0;i<ls;i++){
        int id=s[i]-'a';
        sum[trie[root][id]]-=k;
        if(sum[trie[root][id]]<=0) trie[root][id]=0;
        root=trie[root][id];
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s1>>s;
        if(s1=="insert"){
            ist();
        }else if(s1=="delete"){
            del();
        }else{
            if(src()) cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}