[编程笔记]-Trie_Tree字典树

前言

听起来很高大上，事实上很简单（￣︶￣）

作用

快速存储和查询字符串。

原理

首先建立一颗树，根节点为空节点。

• 插入时，一个字符一个字符地插入，每一个字符都作为上一个字符的子节点存在。如果上一个字符有对应的子节点，就直接进行下一个字符的操作；如果没有，就先新建一个，然后再进行下一步操作。最后一个字符打一个标记，表示这里有一个单词。（如果需要还可以储存下个数）
• 查询时，也是一个字符一个字符查询。如果某个节点没有下一个字符的子节点，或者最后一个节点处没有打标记，就说明没有这个单词，否则就有这个单词。

模板

class trie_tree{
    public:
        int son[N][26],cnt[N],idk;
        void insert(string str){
            int now=0;
            for(int i=0;i<str.size();i++){
                int t=str[i]-'a';
                if(!son[now][t])son[now][t]=++idk;
                now=son[now][t];
            }
            cnt[now]++;
        }
        int find(string str){
            int now=0;
            for(int i=0;i<str.size();i++){
                int t=str[i]-'a';
                if(!son[now][t])return 0;
                now=son[now][t];
            }
            return cnt[now];
        }
}tt;

完结撒花o(￣︶￣)o

写了几篇费脑博客，再写这篇，真的热泪盈眶(≧∇≦)