Trie字符串统计

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值
，只有叶子节点和部分内部节点所对应的键才有相关的值。

步骤分析：

1.son[p][u] p表示当前节点的下标(idx)，同时节点存放的也是当前节点的下标(大小为字符串长度)。u表示当前节点的子节点，只可能有a~z26种可能，u-》 0~25

2.u = str - ‘a’ -> 往下走哪一个字符

默认构造的时候，son[p][u]都是0，除了有字符的节点，其余都是0（根节点和空节点）.

3.if(!son[p][u]) son[p][u] = ++idx;当前节点没有对应字符的子节点，创建一个这样的节点下标

4.p = son[p][u];走到子节点

5.time[p] 代表了以当前节点结尾的字符串出现的个数

for(int i = 0; str[i]; ++i)
{
    u = str[i] - 'a';
    if(!son[p][u])son[p][u] = ++idx;
    p = son[p][u];
}
通过这样一段代码，就实现了从根节点一步步走到单词末尾的节点，最后的p就是末尾节点下标。

特别注意

问题：为什么是++idx，不是idx+ +?

$\cal{Ans:}$ idx初始化是0的话,如果是idx+ +，一开始是son[0][u] = 0，而0代表不存在这样的步骤，这样后面判断的时候，即使相同位置有相同的字符也会再创建一个新的位置
所以要么把idx = 1要么改成+ +idx；

样例

5
I abc
Q abc
Q ab
I ab
Q ab

算法1

$O(1)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], idx, times[N];
char str[N];

void insert(char str[])
{
    /*注意每次p都要赋值0，因为每一次查询或者插入都要从头开始*/
    int p = 0, u;
    /*字符串最后一个字符\0，作为结束条件*/
    for(int i = 0; str[i]; ++i)
    {
        u = str[i] - 'a';
        if(!son[p][u])son[p][u] = ++idx;
        p = son[p][u];
    }
    times[p]++; 
}
int query(char str[])
{
    int p = 0, u;
    for(int i = 0; str[i]; ++i)
    {
        u = str[i] - 'a';
        if(!son[p][u])return 0;
        p = son[p][u];
    }
    return times[p];
}
int main()
{
    int n; cin >> n;
    while(n--)
    {
        char op[2];scanf("%s%s", op, str);
        if(*op == 'I')insert(str);
        else 
            cout << query(str) << endl;
    }

    return 0;
}