【acwing】Trie字符串统计

这篇具有很好参考价值的文章主要介绍了【acwing】Trie字符串统计。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Trie树学习感受

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

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

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

【acwing】Trie字符串统计

从暴力算法看Trie算法

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

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

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

【acwing】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];//返回该字符串的个数
}