Trie树(模板题：AcWing.835)

• 为了节省new新节点所花费的时间，所以用二维数组来表示Trie树
• 用idx来表示用了几个节点
• 二维数组表示节点的存储：一维下标为0说明是根节点

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int[][] son;//一维表示当前节点编号，二维表示儿子节点的下标
    private static int[] cnt;//记录字符串出现了多少次
    private static int idx = 0;//记录一共有几个不同节点

    static void insert(String str){
        char[] c = str.toCharArray();
        int p = 0;
        for(int i = 0; i < str.length(); i++){
            int u = c[i]-'a';
            if(son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    } 

    static int query(String str){
        char[] c = str.toCharArray();
        int p = 0;
        for(int i = 0; i < str.length(); i++){
            int u = c[i]-'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());
        son = new int[N][26];
        cnt = new int[N];
        while(n-- > 0){
            String[] s = br.readLine().split(" ");
            if(s[0].equals("I")){
                insert(s[1]);
            }else{
                System.out.println(query(s[1]));
            }
        }
    }
}