1. 首页
2. 模板
3. 本页

字典树模板

const int MAXN=100100;

char s[MAXN],q[MAXN];
struct Trie
{
    int next[3000100][26],end[3000100];
    int root,L;
    int newnode()
    {
        for(int i=0; i<26; i++) next[L][i]=-1;
        end[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(char *buf)
    {
        int len=strlen(buf);
        int now=root;
        for(int i=0; i<len; i++)
        {
            if(next[now][buf[i]-'a']==-1)
                next[now][buf[i]-'a']=newnode();
            now=next[now][buf[i]-'a'];
            end[now]++;
        }
    }
    void del(char *buf)
    {
        int len=strlen(buf);
        int now=root,x=0,pre=0;
        for(int i=0; i<len; i++)
        {
            pre=now;
            if(next[now][buf[i]-'a']==-1) return ;
            now=next[now][buf[i]-'a'];
        }
        x=end[now];
        now=root;
        for(int i=0; i<len; i++)
        {
            now=next[now][buf[i]-'a'];
            end[now]-=x;
        }
        next[pre][buf[len-1]-'a']=-1;
    }
    bool query(char *buf)
    {
        int len=strlen(buf);
        int now=root;
        for(int i=0; i<len; i++)
        {
            if(next[now][buf[i]-'a']==-1) return false;
            now=next[now][buf[i]-'a'];
            if(end[now]==0) return false;
        }
        return true;
    }
} T;