字符串基础（hash，KMP，AC自动机，trie）

trie树

trie树，又叫字典树，就是把字符串的每个字母看做树上的一个节点，若干个字符串组成了一棵 trie 树。
最一般的trie树好像只能搜索字符串，重点是01trie和可持久化trie树和用trie树来建ac自动机（详见AC自动机）。
这里着重介绍一下01trie
01trie，就是节点代表了数上的二进制位上的数。
可以用来处理位运算。

inline void insert(int x){
    int p=1;
    for(int i=30;i>=0;--i){
        int zc=(x>>i)&1;
        if(!trie[p][zc])trie[p][zc]=++tot;
        p=trie[p][zc];
    }
}//插入的伪代码

P4551 最长异或路径

典题
知道 \(a\otimes b\otimes a=b\)直接处理出来根到每个节点的路径的异或和，关于 \(a\) 节点和 \(b\) 节点之间路径的异或和就是 \(dis_a\otimes dis_b\)，枚举每个节点，此时问题已经转化为在 \(n\) 个数中找出与 \(x\) 异或后最大的数。查找的话对于 \(x\) 二进制下每一位贪心取反就行了，直接拿 trie树就做完了。

#include<bits/stdc++.h>
#define endl '\n'
inline int read(){
    char ch=getchar();int x=0,f=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
const int N=2e5+10;
int n,w[N],head[N],v[N],next[N],tot,val[N];
inline void add(int a,int b,int c){v[++tot]=b,w[tot]=c,next[tot]=head[a],head[a]=tot;}
inline void dfs(int x,int fa){
    for(int i=head[x];i;i=next[i]){
        if(v[i]==fa)continue;
        val[v[i]]=val[x]^w[i];
        dfs(v[i],x);
    }
}
int trie[N<<4][2],_p[35];
inline void insert(int x){
    int p=1;
    for(int i=30;i>=0;--i){
        int zc=(x>>i)&1;
        if(!trie[p][zc])trie[p][zc]=++tot;
        p=trie[p][zc];
    }
}
inline int query(int x){
    int p=1,ans=0;
    for(int i=30;i>=0;--i){
        int zc=(x>>i)&1;
        if(trie[p][zc^1])ans+=_p[i],p=trie[p][zc^1];
        else p=trie[p][zc];
    }
    return ans;
}
signed main(){
    // freopen("in.in","r",stdin),freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    n=read();_p[0]=1;
    for(int i=1;i<=31;++i)_p[i]=_p[i-1]*2;
    if(n==1){std::cout<<0<<'\n';exit(0);}
    for(int i=1;i<n;++i){
        int u=read(),v=read(),w=read();add(u,v,w);add(v,u,w);
    }
    dfs(1,0);int ans=0;tot=1;
    for(int i=1;i<=n;++i)insert(val[i]);
    for(int i=1;i<=n;++i){
        if(ans<=query(val[i]))ans=query(val[i]);
    }
    std::cout<<ans<<'\n';
}

AC自动机

我们知道 KMP 可以做字符串匹配，但是它是单模式匹配，而 AC 自动机相当于把 KMP 放到了 trie 树上，做到了多模式串匹配。