模板应用场景

Trie树是一个快速地存储和查找字符串集合地数据结构，并且一般是纯小写字母，纯大写字母，数字，0或1。混搭较少。
一般涉及两个操作，插入和查询，以下是插入和查询的模板

Trie树字符串模板

const int N=10010;
int s[N][26],cnt[N],idx; //s为记录字符串的路径（存储字符），cnt是记录以某字符节点为结尾的个数
char str[N];

void insert(char str[]){
    int p=0;  //为根节点
    for(int i=0;str[i];i++){
        int u=str[i]-'a';
        if(!s[p][u]) s[p][u]=++idx;
        p=s[p][u];
    }
    cnt[p]++;
}
int query(char str[]){
    int p=0;
    for(int i=0;str[i];i++){
        int u=str[i]-'a';
        if(!s[p][u]) return 0;
        p=s[p][u];
    }
    return cnt[p];
}

最后编辑时间：2021.3.30