基础算法-字典树

Trie

主要是需要一个二维数组int[x][y]保存字典树。用一个一维数组保存该节点是否是字符串的结尾。

例题： https://www.acwing.com/problem/content/837/

代码：

import java.io.*;

public class Main{
    
    private static int N = 100010; 
    private static int[][] trie = new int[N][26];
    private static int idx = 0;
    private static int[] flag = new int[N];
    
    private static void insert(String str){
        int q = 0;
        for(int i = 0 ; i < str.length(); i++){
            int v = str.charAt(i) - 'a';
            if(trie[q][v] == 0){
                trie[q][v] = ++idx;
                q = idx;
            }else{
                q = trie[q][v];
            }
        }
        flag[q] ++;
    } 
    
    private static int query(String str){
        int q = 0;
        for(int i = 0 ;i < str.length(); i++){
            int v =  str.charAt(i) - 'a';
            if(trie[q][v] == 0){
                return 0;
            }else{
                q = trie[q][v];
            }
        }
        return flag[q];
    }
    
    public static void main(String[] args) throws Exception{
        var in = new BufferedReader(new InputStreamReader(System.in));
        var out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(in.readLine());
        while(n > 0){
            n--;
            String[] line = in.readLine().split(" ");
            String op = line[0];
            String str = line[1];
            if(op.equals("I")){
                insert(str);
            }else{
                out.write(String.valueOf(query(str)) + "\n");
            }
        }
        in.close();
        out.close();
    }
    
}