Trie(字典)树模板

模板

int son[N][26], cnt[N], idx;

// 0号点既是根节点，又是空节点

// son[][]存储树中每个节点的子节点

// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串

void insert(char *str)

{

    int p = 0;

    for (int i = 0; str[i]; i ++ )

    {

        int u = str[i] - 'a';

        if (!son[p][u]) son[p][u] = ++ idx;

        p = son[p][u];

    }

    cnt[p] ++ ;

}

// 查询字符串出现的次数

int query(char *str)

{

    int p = 0;

    for (int i = 0; str[i]; i ++ )

    {

        int u = str[i] - 'a';

        if (!son[p][u]) return 0;

        p = son[p][u];

    }

    return cnt[p];

}

一道例题

/**

 * 本质上是一棵树，每个节点都有一个编号，每个节点的孩子节点可能是26个字母的其中之一

 * son[i][j]: 父节点下某个孩子节点的编号(编号为i的节点下（ch-'a'） == j的字母ch的编号)，第一维表示当前点，第二位表示当前点的下一节点

 * cnt[i]:以编号为i的节点为终点的字符串的个数

 * 编号的规定：为0代表根节点或空节点

 */

#include <iostream>

using namespace std;

const int N = 100010;

int n;

int son[N][26], cnt[N], idx;

char str[N];

void insert(char str[])

{

    int p = 0;

    for (int i = 0; str[i]; ++ i)

    {

        int u = str[i] - 'a';

        if (!son[p][u]) son[p][u] = ++ idx; // 如果p节点下映射值为u的孩子节点不存在，那么就添加一个点，编号为idx

        p = son[p][u]; // 当前点指向父节点的下一个节点

    }

    ++ cnt[p]; // 此时p指向的是字符串最后一个字符的节点编号

}

int query(char str[])

{

    int p = 0;

    for (int i = 0; str[i]; ++ i)

    {

        int u = str[i] - 'a';

        if (!son[p][u]) return 0; // 在遍历字符串过程中发现某个字符是不存在的，所以说明当前这个字符串还未曾出现过

        p = son[p][u]; // 开始找下一个字符

    }

    return cnt[p];

}

int main()

{

    cin >> n;

    while (n --)

    {

        char op;

        cin >> op >> str;

        if (op == 'I') insert(str);

        else cout << query(str) << endl;

    }

    return 0;

}

Trie(字典)树模板的相关教程结束。