题目描述

维护一个字符串集合，支持两种操作：
    I x 向集合中插入一个字符串 x；
    Q x 询问一个字符串在集合中出现了多少次。
    共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。

数据范围

1≤N≤2∗1e4

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

注：
    应用Trie字典树者，题目一般限制字母个数为26或52，即大小写字母；
    本Trie树是数组模拟的指针；可以写为：void insert(char *str); int query(char *str);//其余不变
    关于son[N][26]:
        第一维存储表示的是一共有多少个数（将idx赋值给它，而idx是表示到所有的数的），所以第一维要开到N;
        第二维因为下一孩子节点只有小写字母，共26个；
        如插入x，则son[x][0]则表示x的第0个孩子。

注释：
    int son[N][26]; // 其中存放的是：子节点对应的idx。其中son数组的第一维是：父节点对应的idx；
                        第二维计数是其直接子节点，('a' - '0')的值为二维下标。
    int cnt [N];// 以“abc”字符串为例，最后一个字符---'c'对应的idx作为cnt数组的下标。
                    数组的值是该idx对应的个数。
    int idx;// 将该字符串分配的一个树结构中，以下标来记录每一个字符的位置。方便之后的插入和查找。

图示

算法1

#include<iostream>
using namespace std;
const int N=100010;
int son[N][26];//Trie树中每个点的所有孩子
int cnt[N];//以当前点结尾的字符串的数量
int idx;//存储当前用到的点的下标；下标是0的点，既是根节点，又是空节点
char str[N];
void insert(char str[])//存储字符串过程
{
    int p=0;//类似指针，指向树上遍历的当前节点；从根节点出发
    for(int i=0;str[i];i++)//C++中字符串的结尾是'\0'
    {
        int u=str[i]-'a';//将字符串中各个字符映射成0~25
        if(!son[p][u]) //若当前点的孩子不存在
            son[p][u]=++idx;//则创建
        p=son[p][u];//移至下一孩子节点
    }
    cnt[p]++;//以当前点结尾的字符串的数量+1//结束时的标记，也是记录以此节点结束的字符串个数
}
int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;//不存在返回0即可
        p=son[p][u];//存在则下一点
    }
    return cnt[p];
}
int main()
{
    int n;
    scanf("%d",&n);
    char op[2];
    while(n--)
    {
        scanf("%s %s",op,str);
        if(op[0]=='I') insert(str);
        else printf("%d\n",query(str));
    }
    return 0;
}

op要开2个空间的含义:
   %s读取字符串 会有一个’\0’作为字符串的结束，op[1]就是‘\0’

算法2

// package dataStructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created by Yolanda on 2021/5/31 10:24
 */
public class Main {
    private static int N=100010;
    private final static int[][] son =new int[N][26];
    private static int idx;
    private final static int[] cnt=new int[N];
    private char[] str;
    static void insert(char[] str)
    {
        int p=0;//类似指针，指向当前节点
        for (char c : str)//for(int i=0;i<str.length;i++)
        {
            int u = c - 'a';//int u = str[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }
    private static int query(char[] str)
    {
        int p=0;
        for (char c : str) {
            int u = c - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        while(n-->0)
        {
            String ss=br.readLine();
            String[] a=ss.split(" ");
            String op=a[0];
            char[] str=a[1].toCharArray();
            if(op.equals("I")) insert(str);
            else System.out.println(query(str));
        }
    }
}