Trie树

Trie树：用于对字符串进行统计，排序和保存的一种数据结构。每个节点是一个字母(实际代表一个前缀)，若这个节点是一个单词的终末，则其前缀构成的字符串就是这个单词。每个节点可以存放该前缀包含的单词个数，该节点是否是一个单词的终末位置。

用法

插入&前缀统计

插入时，每个访问过到的节点num[]++，不用记录是否是一个单词的末尾

//输入字串用s+1，函数调用用s
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int T[maxn][26];
int num[maxn];
int tot=1;
void add(char *s){
    int l=strlen(s+1);
    int rt=1;
    for(int i=1;i<=l;i++){
        if(T[rt][s[i]-'a']==0){
            T[rt][s[i]-'a']=++tot;
            rt=tot;
        }
        else{
            rt=T[rt][s[i]-'a'];
        }
        num[rt]++;
    }
}
int query(char *s){
    int l=strlen(s+1);
    int rt=1;
    for(int i=1;i<=l;i++){
        if(T[rt][s[i]-'a']==0){
            return 0;
        }
        else rt=T[rt][s[i]-'a'];
    }
    return num[rt];
}
char s[15];
int main(){
    while(1){
        gets(s+1);
        if(s[1]=='')
            break;
        add(s);
    }
    while(~scanf("%s",s+1)){
        printf("%d
",query(s));
    }
}

例题

Prefix Code

给出一系列数字，长度均小于10，问是否有一个数是其他数的前缀？

记录单词的终末，前缀包含的单词个数即可。若一个点是单词终末且前缀包含单词个数>1，则输出No。

//输入字串用s+1，函数调用用s
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int T[maxn][12];
int num[maxn];
int isend[maxn];
int tot=1;
void add(char *s){
    int l=strlen(s+1);
    int rt=1;
    for(int i=1;i<=l;i++){
        if(T[rt][s[i]-'0']==0){
            T[rt][s[i]-'0']=++tot;
            rt=tot;
        }
        else{
            rt=T[rt][s[i]-'0'];
        }
        num[rt]++;
    }
    isend[rt]=1;
}
void init(){
    for(int i=0;i<=tot;i++){
        memset(T[i],0,sizeof(T[i]));
        num[i]=isend[i]=0;
    }
    tot=1;
}
char s[15];
int main(){
    int T;
    cin>>T;
    for(int kase=1;kase<=T;kase++){
        init();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            add(s);
        }
        int flag=1;
        for(int i=1;i<=tot;i++){
            if(isend[i]&&num[i]>1){
                flag=0;
                break;
            }
        }
        if(flag)
            printf("Case #%d: Yes
",kase);
        else
            printf("Case #%d: No
",kase);
    }
}