Trie

作用：高效地存储和查找字符串集合的数据结构

例：存储abcdef,abdef,aced,bcdf,bcff,cdaa,bcdc

存储：用$trie$数组记录节点，第一维为节点编号，大小为字符串总长度，第二维记录当前节点的对应字符的子节点，大小为字符种类数，$cnt$数组记录每个节点对应的单词数量，$idx$记录当前已使用节点数。

1	int trie[N][30],cnt[N],idx;

插入：

判断当前节点的子节点是否包含当前字母，若不包含，新建一个节点，跳到下一节点
当遍历到当前单词最后一个字符时，标记当前节点，表示当前节点有一个单词

void insert(string s){
    int p=0,len=s.length()-1;
    for(int i=0;i<=len;i++){
        if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++idx;
        p=trie[p][s[i]-'a'];
    }
    cnt[p]++;
}

查找：

判断当前节点的子节点是否包含当前字母，若不包含，说明没有该单词，返回$0$，否则跳到下一节点
当遍历到当前单词最后一个字符时，返回当前节点的$cnt$，表示当前节点的单词数量。

int find(string s){
    int p=0,len=s.length()-1;
    for(int i=0;i<=len;i++){
        if(!trie[p][s[i]-'a'])return 0;
        p=trie[p][s[i]-'a'];
    }
    return cnt[p];
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。