定义：

将多个字符串以树的方式存储即为字典树，如图，\(1,4,3,12\) 表示 \(cca\) ，我么用 \(ch[i][j]\) 来表示第 \(i\) 个节点的 \(j\) 字符所指向的下一个节点，\(tag[u]\) 表示节点 \(u\) 是否代表一个字符串的结尾，如果是的话，\(tag[u]=1\)。

模板CODE

添加字符串

//n表示即将要向字典树插入n个字符串
const N 100005;
scanf("%d",&n);
    for (int i=1;i<=n;i++){
        char s[N];
        scanf("%s",s+1);
        int u=1;
        for (int j=1;s[j];j++){
            int c=s[j]-'a';
            if (!ch[u][c]) ch[u][c]=++tot;
            u=ch[u][c];
        }
        tag[u]=1;
    }

字符串查找

//查看字符串s是否在字典树当中，如果在输出OK，否则输出WRONG
char s[N];
scanf("%s",s+1);
        int u=1;
        for (int i=1;s[i];i++){
            int c=s[i]-'a';
            u=ch[u][c];
            if (!u) break;
        }
        if (tag[u]==1){
            puts("OK");
            continue;
        }
        else {
            puts("WRONG");
            continue;
        }

例题

(P2580 于是他错误的点名开始了)[https://www.luogu.com.cn/problem/P2580]

维护异或极值

待补充