题解 | #字典树的实现#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        // 注意 hasNext 和 hasNextLine 的区别
        String line = null;
        while ((line = in.readLine()) != null) { // 注意 while 处理多个 case
            int m = Integer.parseInt(line);
            Trie trie = new Trie();
            trie.build();
            for (int i = 0; i < m; i++) {

                String[] lines = in.readLine().split(" ");
                int op = Integer.parseInt(lines[0]);
                String world = lines[1];
                if (op == 1) {
                    trie.insert(world);
                } else if (op == 2) {
                    trie.delete(world);
                } else if (op == 3) {
                    int yes = trie.search(world);
                    out.println(yes > 0 ? "YES" : "NO");
                } else if (op == 4) {
                    out.println(trie.prefixNumber(world));
                }
            }
            trie.clear();
        }
        out.flush();
        out.close();
        in.close();
    }

    static class Trie {
        private static int MAXN = 150001;
        private int[] pass = new int[MAXN];
        private int[] end = new int[MAXN];
        private int[][] nexts = new int[MAXN][26];
        private int cnt;
        public void build() {
            cnt = 1;
        }
        public void clear() {
            for (int i = 0; i < cnt; i++) {
                Arrays.fill(nexts[i], 0);
                pass[i] = 0;
                end[i] = 0;
            }
        }
        public void insert(String word) {
            int n = word.length();
            int cur = 1;
            pass[cur]++;
            for (int i = 0; i < n; i++) {
                int path = word.charAt(i) - 'a';
                if (nexts[cur][path] == 0) {
                    nexts[cur][path] = ++cnt;
                }
                cur = nexts[cur][path];
                pass[cur]++;
            }
            end[cur]++;
        }

        public void delete(String word) {
            if (search(word) <= 0) {
                return;
            }
            int cur = 1;
            int n = word.length();
            for (int i = 0; i < n; i++) {
                int path = word.charAt(i) - 'a';
                if (--pass[nexts[cur][path]] == 0) {
                    nexts[cur][path] = 0;
                    return;
                }
                cur = nexts[cur][path];
            }
            end[cur]--;
        }
        public int search(String word) {
            int cur = 1;
            int n = word.length();
            for (int i = 0; i < n; i++) {
                int path = word.charAt(i) - 'a';
                if (nexts[cur][path] == 0) {
                    return 0;
                }
                cur = nexts[cur][path];
            }
            return end[cur];
        }

        public int prefixNumber(String pre) {
            int cur = 1;
            int n = pre.length();
            for (int i = 0; i < n; i++) {
                int path = pre.charAt(i) - 'a';
                if (nexts[cur][path] == 0) {
                    return 0;
                }
                cur = nexts[cur][path];
            }
            return pass[cur];
        }
    }
}