OIer - FankerWang

一个不正经的信息学博客

字典树(Trie Tree)的使用

问题一

已知有n个长度不一定相同的母串,以及一个长度为m的模式串T,求该模式串是否是其中一个母串的前缀。如果将模式串T挨个去比较,则算法复杂度会很高,达到O(n×m),是否有高效的方法呢?

问题二

已知一个长度为n的字符串S,求该字符串中有多少个不相同的子串。朴素做法可以先枚举出所有的子串,这样时间复杂度为O(n^2),之后再去重,直接做算法复杂度很高,改成Hash或者用set、map处理,整体复杂度仍然会很高。


以上两个问题可以用Trie树高效求解。
Trie树又称字典树或者单词查找树,是一种树形的数据结构,支持字符串的插入和查询操作,常用于大量字符串的检索、去重、排序等。Trie树利用字符串的公共前缀,逐层建立起一颗多叉树。在检索时类似于在字典中查单词,从第一个字符开始遍历,在Trie树中一层一层往下查找,查找效率可以达到O(n)n为查找字符串的长度。
下图是一棵以词:atoteatedteniininn构成的字典树,其中带下划线的节点为终端节点(从根节点到终端节点的遍历过程就是Trie中存储的一个字符串)。
《字典树(Trie Tree)的使用》
Trie树有以下特点:
1. Trie树的根节点上不存储字符,其余节点上存且只存一个字符。
2. 从根节点出发,到某一节点上经过的字符,即是该节点对应的前缀。
3. 每个节点的孩子节点存储的字符各不相同。
4. Trie树牺牲空间来换取时间,当数据量很大时,会占用很大空间。如果字符串均由小写字母组成,则每个节点最多会有26个孩子节点,则最多会有26^n个用于存储的节点,n为字符串的最大长度。

Trie树常用于字符串的快速检索,字符串的快速排序与去重,文本的字频统计等。

基本操作

数据结构

const int MAX_N = 10000;  // Trie 树上的最大结点数
struct Trie {
    int ch[MAX_N][26];  // ch 保存了每个结点的 26 个可能的子结点编号,26 对应着 26 种小写字母,也就是说,插入的字符串全部由小写字母组成。初始全部为 -1
    int tot;  // 总结点个数,初始为 0
    int cnt[MAX_N];  // 每个结点

    void init() {  // 初始化 Trie 树
        tot = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(ch, -1, sizeof(ch));
    }
};

插入
从根节点开始,按字符串中当前字符出边,走到对应的节点。若没有这样的节点,则新开一个节点。

void insert(char *str) {
    int p = 0;  // 从根结点(0)出发
    for (int i = 0; str[i]; ++i) {
        if (ch[p][str[i] - 'a'] == -1) {  // 该子结点不存在
            ch[p][str[i] - 'a'] = ++tot;  // 新增结点
        } 
        p = ch[p][str[i] - 'a'];  // 在 Trie 树上继续插入字符串 str
    }
    cnt[p]++;
}

查询
从根节点开始,按当前字符出边,走到对应的节点。若没有这样的节点,则不存在;若读完字符串的节点也不是终止节点,也不存在。

int find(char *str) {  // 返回字符串 str 的出现次数
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        if (ch[p][str[i] - 'a'] == -1) {
            return 0;
        }
        p = ch[p][str[i] - 'a'];
    }
    return cnt[p];
}

内存动态分配

在实现字典树时在实现字典树时,有时候会发现如果按照题目要求来开辟内存空间,会导致内存超出题目限制。这时,可以使用内存动态分配的小技巧。在之前给出的 Trie 树代码中,无论树上的结点是否是叶子结点,都给它开辟了大小为MAX_C那么大的子节点指针数组。我们可以在一个节点一定有子节点的时候再开辟大小为MAX_C的子节点指针数组,可以减小很多不必要的内存开销。

const int MAX_N = 10000;  // Trie 树上的最大结点数
const int MAX_C = 26;  // 每个结点的子结点个数上限
struct Trie {
    int *ch[MAX_N];  // ch 保存了每个结点的 26 个可能的子结点编号,26 对应着 26 种小写字母,也就是说,插入的字符串全部由小写字母组成。初始全部为 -1
    int tot;  // 总结点个数(不含根结点),初始为 0
    int cnt[MAX_N];  // 以当前结点为终端结点的 Trie 树中的字符串个数

    void init() {  // 初始化 Trie 树,根结点编号始终为 0
        tot = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(ch, 0, sizeof(ch));  // 将 ch 中的元素初始化为 NULL
    }

    void insert(char *str) {
        int p = 0;  // 从根结点(0)出发
        for (int i = 0; str[i]; ++i) {
            if (ch[p] == NULL) {
                ch[p] = new int[MAX_C];  // 只有 p 当包含子结点的时候才去开辟 ch[p] 的空间
                memset(ch[p], -1, sizeof(int) * MAX_C);  // 初始化为 -1
            }
            if (ch[p][str[i] - 'a'] == -1) {  // 该子结点不存在
                ch[p][str[i] - 'a'] = ++tot;  // 新增结点
            } 
            p = ch[p][str[i] - 'a'];  // 在 Trie 树上继续插入字符串 str
        }
        cnt[p]++;
    }

    int find(char *str) {  // 返回字符串 str 的出现次数
        int p = 0;
        for (int i = 0; str[i]; ++i) {
            if (ch[p][str[i] - 'a'] == -1) {
                return 0;
            }
            p = ch[p][str[i] - 'a'];
        }
        return cnt[p];
    }
};
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注