【acwing】Trie字符串统计

Trie树 学习感受

相比于之前学习的kmp匹配算法,Trie树的实现还是非常好理解的。(kmp算法太难了orz)

从直观的模拟过程来看,trie树就像一颗树一样,从上(根节点)到下(叶节点)有序串联起来组成一个字符串。

每一个额外标记结束的位置表示字符串的结束,通过计算标记数即可指导一共有多少该字符串。

 

 

从暴力算法看Trie算法

先想想,如果要是暴力算法来做的话,应该怎么去统计字符串出现次数呢?

首先要利用数组去存储各种不相同的字符串,在读入一个新的字符串时,需要先判断他和已有的字符串是否相等,如果不相等,则将该字符串存入,如果相等,则跳过该字符串。显然,暴力算法的时间复杂度会很大。在这里,有没有更好的判断方法,让我不用再去每次判断都要遍历所有已经储存的字符串呢?

我们来着重讨论判断他和已有字符串是否相等,在这里的判断方法显然是循环遍历两个字符串,判断字符串长度以及每个位置是否相等。那么,在循环遍历所有字符串的过程中,不难发现,对于部分相等以及完全相等字符串,从字符串第一个字符起,总会和目标字符串有一个公共部分。那么,我们是否可以对于字符串每一个位置(对于数的每一层)只存储一个字符串该位置出现的字符,使得所有字符串共用一颗树(如上图)。这样在大大减少时间复杂度的同时,空间复杂度也得到的减小。

Trie树的实现

Trie树的实现过程是用数组模拟实现多叉树的过程。首先需要一个二维数组 trie[n][m] 来实现树。其中 n 代表所有字符的总长度,m代表多叉树的最大分支。

再者,需要一个 cnt[n] 数组存储每个字符串出现的次数,n应该小于所有字符的总数量。

最后,需要一个整型变量 idx , 用于存储树中某个节点对应 cnt 数组的下标。

 

树的插入代码如下:

void insert(string s)
{
    int tmp = 0;//tmp 代表当前节点的位置,0 代表根节点 
    for(auto c : s)
    {
        int u = c - 'a';//将二十六个字母映射到0到25
        if(!trie[tmp][u]) trie[tmp][u] = ++ idx;//如果字典树当前位置当中没有这个字符,则建立这个字符,且将他与cnt数组对应
        tmp = trie[tmp][u];//类比指针,指向字典树下一个位置
    }
    cnt[tmp] ++;//把字符串结束对应的点的计数数组增加一
}

树的查询代码如下:

int search(string s)
{
    int tmp = 0;//tmp 代表当前节点的位置,0 代表根节点 
    for(auto c : s)
    {
        int u = c - 'a';//将二十六个字母映射到0到25
        if(!trie[tmp][u]) return 0;//如果字典树当前位置当中没有这个字符,则查询结束,证明没有这个字符串
        else tmp = trie[tmp][u];//类比指针,指向字典树下一个位置
    }
    return cnt[tmp];//返回该字符串的个数
}

 

热门相关:冉冉心动   重生当学神,又又又考第一了!   豪门重生盛世闲女   梦回大明春   朕是红颜祸水