题目描述

维护一个字符串集合，支持两种操作：

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

输入格式
第一行包含整数N，表示操作数。

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

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

每个结果占一行。

数据范围
1≤N≤2∗104
输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

算法1

思路

1.Trie树是将一个字符串拆分成字符数组一个个插入

2.当插入第一个字符时判断空节点下有无第一个节点，有则指针往下移，无就创建一个（赋地址值），

因此需要全局变量c[N][26]:n节点的下一个0~26节点， idx：唯一地址值

3.统计字符串数量时只需字符串最后一个字符(节点地址)的数量，

因此需要全局变量k[]:存储最后一个字符(节点地址)的数量

Java 代码

import java.util.*;

public class Main{
    private static int N = 100010;
    private static int[] k =new int[N];           //以该节点结尾的字符串的个数
    private static int[][] c = new int[N][26];    //c['a']['b']:a节点的下一个b节点
    private static int idx = 1;               //节点地址,0位置为空节点所以从1开始

    public static void insert(char[] arr){
        //p一开始指向空节点
        int p = 0;
        for(int i = 0;i < arr.length;i++){
            int s = arr[i] - 'a';
            if(c[p][s] == 0){
                //p的下一个s节点为空，就赋值地址
                c[p][s] = idx++;
            }
            //p指向下一个节点
            p = c[p][s];
        }
        //以p节点结尾的字符串+1
        k[p]++;
    }
    public static int query(char[] arr){
        int p = 0;
        for(int i = 0;i < arr.length;i++){
            int s = arr[i] - 'a';
            if(c[p][s] == 0){
                //p的下一个s节点为空，则无此字符串
                return 0;
            }
            p = c[p][s];
        }
        return k[p];
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-- > 0){
            String opt = scanner.next();
            String str = scanner.next();
            if("I".equals(opt)){
                insert(str.toCharArray());
            }else if("Q".equals(opt)){
                System.out.println(query(str.toCharArray()));
            }
        }
    }
}