字典树

#include <bits/stdc++.h>
using namespace std;

#ifndef _TRIE_
#define _TRIE_
#define ll int
#define MAXN 100005
#define MAXCHAR 128

//字典树
struct Trie {
    ll cnt;                     // 动态开点（开 Trie 树结点编号）
    ll next[MAXN][MAXCHAR];     // 记录关联边为对应字符的子结点的下表
    bool exist[MAXN];           // 记录以该结点结尾的字符串是否存在
    Trie(): cnt(0) {}
    // 插入字符串
    void insert(char *str, ll len) {
        ll p = 0;
        for(ll i = 0; i < len; ++i) {
            ll c = str[i];
            if(!next[p][c]) {
                next[p][c] = ++cnt;
            }
            p = next[p][c];
        }
        exist[p] = 1;
    }
    // 查找字符串
    bool find(char *str, ll len) {
        ll p = 0;
        for(ll i = 0; i < len; ++i) {
            ll c = str[i];
            if(!next[p][c]) {
                return false;
            }
            p = next[p][c];
        }
        return exist[p];
    }
};
#endif