题目描述

用trie树来存储字符串,字符串均由字母构成

背模板时需要理清的思路

下标是0的点既是根节点,又是空节点。如果输入的是字符串的话，字符串中的每个字母就对应每个节点。

①son[N][26]存的是当前这个节点的编号.cnt[N]数组存储的是以当前这个点结尾的字符串有多少个,idx是当前已存入的最后一个节点的下标。
②插入操作中的过程主要有两步,第一步是从树顶判断输入字符串字母开头子节点是否存在。第二步就是延伸节点存储。p的意思是从开头字符相同的地方开始访问该字符串。存储完毕后在结尾处让cnt++代表该条字符串已被存储。
p跟idx的区别在于p的起点是已存入的第一个相同节点开始遍历的，用的就是idx的值去遍历的，

代码写法上的特点

①char a[2]的字符数组可以用%s来输入

参考文献

参考y总的代码和视频讲解下面的评论

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int cnt[N], son[N][26], idx;
int n;
char str[N];

void insert(char str[])
{
    int p = 0;
    // cout << 3;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
        // cout << 1;
    cnt[p] ++ ;
}

int query(char str[])
{
    int p = 0;
        // cout << 2;
    for (int i = 0; str[i]; i ++ )
    {
        // cout << 1;
        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[2];
        scanf("%s%s", &op, &str);

        if (op[0] == 'I') insert(str);
        else {
            int k = query(str);
            printf("%d\n", k);
        }

    }
    return 0;

}