trie树

1. trie树的作用是高效的查询和存储字符串的

题目描述

插入字符串和查询字符串拆入的个数

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

算法1

(trie) $O(n)$

思路
    - 以树的形式拆入，如果是最后一个节点要做一个标记
    - 以树的形式查询

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[][] son = new int[N][26];// 存储所有子节点
    static int[] cnt = new int[N]; // 已当前节点结尾的字符串的个数
    static int idx;// 当前节点

    static int insert(char[] str){
        int p = 0;// 0 代表根节点 也代表的是最后一个叶子节点
        for (int i = 0; i < str.length; i++){// 遍历字符串
            int u = str[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;// 不存在的话，创建一个节点
            p = son[p][u];// 获取当前节点
        }
        return cnt[p]++;
    }

    static int query(char[] str){
        int p = 0;
        for (int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        while (n-->0){
            String[] s = scan.nextLine().split(" ");
            if (s[0].equals("I")){
                insert(s[1].toCharArray());
            }else{
                System.out.println(query(s[1].toCharArray()));
            }
        }
    }
}