8-Trie树

算法思想

算法图解

算法模板

import java.util.*;

public class Main {
    static int N = 100010;
    // 一个字母即为一个节点
    // son[i][] 存储第 i 个节点的子节点的索引（在 cnt 数组中的索引）
    // son[0] 为根节点，同时也是个空节点
    static int[][] son = new int[N][26];
    // cnt[i] 存储以第 i 个节点结尾的单词的数量
    static int[] cnt = new int[N];
    // idx 表示 cnt 数组当中最后一个已被使用的元素的索引
    // idx 初始化为0，表示 cnt 数组当中最后一个已被使用的元素的索引为 0
    static int idx = 0;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while(n -- > 0)
        {
            String op = in.next();
            var chars = in.next().toCharArray();
            if(op.equals("I"))
            {
                insert(chars);
            }
            else 
            {
                int res = query(chars);
                System.out.println(res);
            }
        }
    }
    
    static void insert(char[] chars)
    {
        int p = 0;
        for(char ch : chars)
        {
            int u = ch - 'a';
            if(son[p][u] == 0) son[p][u] = ++ idx;
            p = son[p][u];
        }
        cnt[p] ++; 
    }
    
    static int query(char[] chars)
    {
        int p = 0;
        for(char ch : chars)
        {
            int u = ch - 'a';
            if(son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
}