字典树(前缀树)

图片来源:百度百科

功能在o(n）的时间插入和查询字符串，n是字符串长度

1.静态

#include
using namespace std;
const int N=1e6+10;
int son[N][26],cnt[N],idx;//cnt表示该字符串的数量，son表示字符串的某个字符的下一个节点的位置，其中字符串最后一个字符的son值表示该字符串的编号
int n,m;
string str;
void insert()//插入字符串
{
    int p=0;
    for(int i=0;i>n>>m;
    while(n--)
    {
        cin>>str;
        insert();
    }
    while(m--)
    {
        cin>>str;
        cout< 
2.动态(来源:力扣)
 
class Trie {
private:
    vector children;
    bool isEnd;

    Trie* searchPrefix(string prefix)
    {
        Trie* node=this;
        for(char ch:prefix)
        {
            ch-='a';
            if(node->children[ch]==nullptr)
                return nullptr;
            node=node->children[ch];
        }
        return node;
    }
public:
    Trie() :children(26),isEnd(false){}
    
    void insert(string word) {
        Trie *node=this;
        for(char ch:word)
        {
            ch-='a';
            if(node->children[ch]==nullptr)
                node->children[ch]=new Trie();
            node=node->children[ch];
        }
        node->isEnd=true;
    }
    
    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node!=nullptr&&node->isEnd;
    }
    
    bool startsWith(string prefix) {
        return this->searchPrefix(prefix)!=nullptr;
    }
};