题目描述

Trie树字符串统计

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static final int N = 100010;

    //初始化需要准备 
    //son[N][26]N父节点下的子节点(26)  
    //cnt[]对结束节点打标记 
    //idx->作用是记录每个不同的组合的数字
    static int[][] son = new int [N][26];
    static int[] cnt = new int[N];
    static int idx = 0;

    static void insert(String s){
        int p = 0;
        for (int i = 0; i < s.length(); i++){
            //获取 ACSS码转换成数字
            int u = s.charAt(i) - 'a';
            //如果当前组合不存在, 则创建
            if(son[p][u] == 0){
                son[p][u] = ++idx;
            }
            //更新到下个节点
            p = son[p][u];
        }
        cnt[p] ++;
    }
    static int query(String s){
        int p = 0;
        for (int i =0; i< s.length(); i++){
            int u = s.charAt(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 in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt( in.readLine());

        while(n-->0){

            String[] s1 = in.readLine().split(" ");
            String c = s1[0];
            String str = s1[1];
            if(c.equals("I")){
                insert(str);
            }else{
                System.out.println(query(str));
            }
        }

    }
}