字典树

字典树

Trie是一种存储字符串的树形数据结构，除了根节点，每个节点都可以存储一个字符，从根节点到树上某一节点的路径代表一个字符串

数据结构

数组

const int MAXNODE = 10010; // 最大节点数
const int charsize = 26; // 字符集大小
int node[MAXNODE][charsize]; // 记录节点编号
bool isend[MAXNODE]; // 代表此编号节点是否为终止节点
int root = 0; // 代表根节点编号
int cnt = 0; // 当前节点数

指针

struct TreeNode {
    TreeNode *children[charsize];
    bool isend;
} *root;

字典树的插入

void insert(char s[], int len) {
    int now = 0;
    for (int i = 0; i < len; i++) {
        int x = s[i] - 'a';
        if (!node[now][x]) {
            node[now][x] = ++cnt;
        }
        now = node[now][x];
    }
    isend[now] = 1;
}

字典树的查找

bool search(char s[], int len) {
    int now = 0;
    for (int i = 0; i < len; i++) {
        int x = s[i] - 'a';
        if (!node[now][x]) {
            return false;
        }
        now = node[now][x];
    }
    return isend[now];
}