Trie——字典树多模式匹配

Trie的形态是一棵多叉树，存储的信息是一个个串。
trie最最最基本的功能：插入、删除
1.插入
对于要插入的串，我们将该串从前往后把每个字符顺次插入到树中，我们从树的根开始，假设当前在树上的u节点，要插入c字符，我们先看u节点有没有c边，如果有则将u走向该边连向的节点，如果没有我们就给当前节点连一条c边，然后将u走向该边连着的点。一般我们会在每个串的最后一个字符的位置加一个lable，表示该点是一个串的末尾。
2.删除：
对于要删除的串，我们最好开一个cnt数组，当插入一个串时，每遍历到一个节点，我们就让cnt++。这样一来，当我们需要删除时，我们并不是真的将某个节点删除，而是将每个节点的cnt–。

void insert(char s[])
{
    int u=0;
    cnt[u]++;
    for(int i=0;s[i];i++)
    {
        if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++idx;
        u=tr[u][s[i]-'a'];
        cnt[u]++;
    }
    lable[u]=true;
}
void del(char s[])
{
    int u=0;
    cnt[u]--;
    for(int i=0;s[i];i--)
    {
        u=tr[u][s[i]-'a'];
        cnt[u]--;
    }
    lable=false;
}

trie解决的最基本的问题：给我们n个串si,再给我们一个串t，问我们t是否在s中出现过。
如果不用trie解决，我们需要一个一个的去匹配，时间复杂度为O(n*|t|)。
现在有了trie，我们只需要从根开始，像插入时那样一个一个字符往下找，如果中间某个字符没出现，则不存在该串。

bool query(char s[])
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        if(!tr[u][s[i]-'a'])return false;
        u=tr[u][s[i]-'a'];
    }
    if(lable[u])return true;
    return false;
}

例题： https://ac.nowcoder.com/acm/problem/15049 假的字符串
按照题意，一个字符串最小需要满足两个条件：
1.其他串不是自己的前缀
2.该串的每个字符都要比兄弟字符要小（不能出现矛盾）
我们从根开始查找，查找时将当前字符向兄弟字符连一条边，表示当前字符小于兄弟字符，当我们查找到该分支的第一个 lable为true的点时，停下来，然后判断刚刚连的那些边构不构成环，如果不构成就说明没矛盾，该串可以成为最小串。回溯即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int tr[N][30],idx;
int n;
string s[30010];
int cnt[N],alp[N];
int ans[30010],tt;
vector<int>h[30];
int ind[30],outd[30];
void insert(string s,int t)
{
    int u=0;
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        if(!tr[u][s[i]-'a'])
        {
            tr[u][s[i]-'a']=++idx;
            alp[idx]=s[i]-'a';
        }
        u=tr[u][s[i]-'a'];
    }
    cnt[u]=t;
}
bool topsort()
{
    int q[30]={};
    int inn[30];
    memcpy(inn,ind,sizeof ind);
    int tt=0,hh=0;
    for(int i=0;i<26;i++)if(inn[i]==0)q[tt++]=i;
    while(hh!=tt)
    {
        int t=q[hh++];
        for(auto p:h[t])
        {
            if(--inn[p]==0)q[tt++]=p;
        }
    }
    return tt==26;
}
void dfs(int u,int fa)
{
    if(u)
    {
        int x=alp[u];
        for(int i=0;i<26;i++)
        {
            if(!tr[fa][i])continue;
            int y=alp[tr[fa][i]];
            if(x!=y)
            {
                h[x].push_back(y);
                ind[y]++,outd[x]++;
            }
        }
    }
    if(cnt[u])
    {
        if(topsort())ans[tt++]=cnt[u];
        return;
    }
    for(int i=0;i<26;i++)
    {
        if(tr[u][i])
        {
            dfs(tr[u][i],u);
            int x=alp[tr[u][i]];
            for(int j=0;j<26;j++)
            {
                if(!tr[u][j])continue;
                int y=alp[tr[u][j]];
                if(x!=y)
                {
                    ind[y]--;
                    outd[x]--;
                    h[x].pop_back();
                }
            }            
        }

    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        insert(s[i],i);
    }
    dfs(0,-1);
    sort(ans,ans+tt);
    cout<<tt<<endl; 
    for(int i=0;i<tt;i++)cout<<s[ans[i]]<<endl;
    return 0;
}

01Trie

01Trie就是将一个个的二进制数当作串从高位依次插入到树中。
解决的问题——异或和
对于异或运算我们知道：假设a^b=c，则c^a=b，因此我们常常可以配合前缀和完成不错的操作
例题： https://ac.nowcoder.com/acm/problem/50993 The XOR Largest Pair
我们将给的序列插入到树中，然后我们需要枚举每个数，从trie中找到一个数跟他异或最大，最后取一个max即可。那如何从trie中找一个数跟x异或最大呢。从根节点开始，假设x的这一位是t，每次优先往t^1的边上走，因为异或运算只有0^1=1(最大)。这样找到的数就是和x异或最大的数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = N*32;
int tr[M][2],idx;
int n;
int a[N];
int ans;
void insert(int x)
{
    int u=0;
    for(int i=30;i>=0;i--)
    {
        int t=(x>>i)&1;
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
}
int query(int x)
{
    int res=0;
    int u=0;
    for(int i=30;i>=0;i--)
    {
        int t=(x>>i)&1;
        if(tr[u][t^1])
        {
            u=tr[u][t^1];
            res+=1<<i;
        }
        else u=tr[u][t];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,query(a[i]));
    }
    cout<<ans;
    return 0;
}

例题： https://ac.nowcoder.com/acm/problem/22998 奶牛异或
该题和上一题的区别在于上一题是两个数异或，现在是一个区间的数异或，由于异或运算的性质我们知道一个区间的异或可以由前缀和得到，假设我们要求[l,r]的异或和，我们只需要用s[r]^s[l-1]即可得到(s是前缀和数组)。所以我们将前缀和数组插入到树中，枚举右端点，然后从根开始找，假设s[r]当前位是t，优先往t^1的边走(需要保证走到的节点包含0~r-1的前缀和信息)。即可得到答案。那如何判断一个节点是否包含[0,i]的信息呢，我们可以为每一个节点开一个minn数组，插入时维护即可。这只解决了问题的一半，我们还需要保证如果有多个区间的异或和都是最大的，答案应该是长度最短的，我们可以为每个节点开一个数组，插入时将当前前缀和的编号存进遍历到的节点里，这样就可以在查询时可以二分求出每个答案的最短长度，最后再取一个min。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N = 1e5+10,M = N*22;
int tr[M][2],idx;
int minn[M];
unordered_map<int,vector<int>>S;
int n;
int s[N];
PII ans[N];
int maxn;
void insert(int x,int p)
{
    int u=0;
    minn[u]=min(minn[u],p);
    for(int i=21;i>=0;i--)
    {
        int t=(x>>i)&1;
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
        minn[u]=min(minn[u],p);
    }
    S[u].push_back(p);
}
PII query(int x)
{
    int res=0;
    int xx=s[x];
    int u=0;
    for(int i=21;i>=0;i--)
    {
        int t=(xx>>i)&1;
        if(tr[u][t^1]&&minn[tr[u][t^1]]<x)res+=1<<i,u=tr[u][t^1];
        else u=tr[u][t];
    }
    maxn=max(maxn,res);
    if(S[u].size()==1)return {res,S[u][0]+1};
    int l=0,r=S[u].size()-1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(S[u][mid]<x)l=mid;
        else r=mid-1;
    }
    return {res,S[u][l]+1};
}
int main()
{
    memset(minn,0x3f,sizeof minn);
    cin>>n;
    insert(0,0);
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]^=s[i-1];
        insert(s[i],i);
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]=query(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(maxn==ans[i].first)
        {
            cout<<maxn<<" "<<ans[i].second<<" "<<i;
            break;
        }
    }
    return 0;
}

可持久化Trie

每次插入一个点我们就新建一个版本，当前串的节点全部新建，其余的连向上一个版本。
例题： https://ac.nowcoder.com/acm/problem/51120 最大异或和
给我们一个区间[l,r]和x，从该区间找一个点p，令a[p]^a[p+1]^…^a[n]^x最大。同样可以用前缀和的思想把该式子变成s[n]^s[p-1]^x=s[p-1]^s[n]^x，s[n]^x是定值，设为c，则问题变为从区间[l-1,r-1]找一个点q使s[q]^c最大。如果是从[0,r-1]找我们可以用刚才上面那道题的解法做出来，但是现在左边界不是0了，我们需要换一种方法，我们可以建一颗可持久化Trie，考虑第r-1个版本，这样右边界就不需要考虑了，然后从根开始找，设c在该位是t，则优先往t^1的方向走(需要保证走的节点包含大于等于l-1的前缀和信息)，问题就解决了。

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5+10,M = N*25;
int tr[M][2],idx,root[N],maxid[M];
int n,m;
int s[N];
void insert(int i,int k,int p,int q)  //递归插入
{
    if(k<0)
    {
        maxid[q]=i;
        return;
    }
    int v=s[i]>>k&1;
    if(p)tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    insert(i,k-1,tr[p][v],tr[q][v]);
    maxid[q]=i;
}
void insert(int i,int p,int q)   //迭代插入
{
    maxid[q]=i;
    for(int k=23;k>=0;k--)
    {
        int t=s[i]>>k&1;
        if(p)tr[q][t^1]=tr[p][t^1];
        tr[q][t]=++idx;
        p=tr[p][t];
        q=tr[q][t];        
        maxid[q]=i;
    }
}
int query(int l,int root,int x)
{
    for(int i=23;i>=0;i--)
    {
        int t=x>>i&1;
        if(maxid[tr[root][t^1]]>=l)root=tr[root][t^1];
        else root=tr[root][t];
    }
    return x^s[maxid[root]];
}
int main()
{
    cin>>n>>m;
    maxid[0]=-1;
    root[0]=++idx;
    insert(0,0,root[0]);
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]^=s[i-1];
        root[i]=++idx;
        insert(i,root[i-1],root[i]);
    }
    while(m--)
    {
        char op[3];
        cin>>op;
        if(*op=='A')
        {
            cin>>s[++n];
            s[n]^=s[n-1];
            root[n]=++idx;
            insert(n,root[n-1],root[n]);
        }
        else
        {
            int l,r,x;
            cin>>l>>r>>x;
            cout<<query(l-1,root[r-1],s[n]^x)<<endl;
        }
    }
    return 0;
}