一. 题目

1. 数组版

2. 指针版

二. 思路

三. 代码

1. 数组版

import java.io.*;

public class Main
{
    static final int N = (int) 1e5 + 10, M = 30;
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] rs;

    int n, idx;
    int[] cnt = new int[N];//统计出现次数
    int[][] tr = new int[N][M];//第一维表示所有字符最大总和, 根为0

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.work();
    }

    void add(String s)
    {
        int p = 0;//上一层的节点，初始为根
        for (Character c : s.toCharArray())
        {
            int v = c - 'a';
            if (tr[p][v] == 0) tr[p][v] = ++idx;
            p = tr[p][v];
        }
        ++cnt[p];
    }

    int query(String s)
    {
        int p = 0;
        for (Character c : s.toCharArray())
        {
            int v = c - 'a';
            if (tr[p][v] == 0) return 0;
            p = tr[p][v];
        }
        return cnt[p];
    }

    void work() throws Exception
    {
        n = Integer.parseInt(br.readLine());

        StringBuilder ans = new StringBuilder();
        while (n-- > 0)
        {
            rs = br.readLine().split(" ");
            if ("I".equals(rs[0])) add(rs[1]);
            else ans.append(query(rs[1])).append('\n');
        }
        bw.write(ans.toString());
        bw.close();
    }
}

2. 指针版

class Trie
{
    private static class Node
    {
        char c;
        int cnt;
        Map<Character, Node> ne;//或者用数组存

        public Node()
        {
        }

        public Node(char c, int cnt, Map<Character, Node> ne)
        {
            this.c = c;
            this.cnt = cnt;
            this.ne = ne;
        }
    }

    final Node vh = new Node();

    public Trie()
    {
        vh.ne = null;
    }

    public void insert(String word)
    {
        Node p = vh;
        for (Character c : word.toCharArray())
        {
            if (p.ne == null) p.ne = new HashMap<>();
            if (!p.ne.containsKey(c))
            {
                Node node = new Node(c, 0, null);
                p.ne.put(c, node);
            }
            p = p.ne.get(c);
        }
        ++p.cnt;
    }

    public boolean search(String word)
    {
        Node p = vh;
        for (Character c : word.toCharArray())
        {
            if (p.ne == null) return false;
            if (!p.ne.containsKey(c)) return false;
            p = p.ne.get(c);
        }
        return p.cnt > 0;
    }

    public boolean startsWith(String prefix)
    {
        Node p = vh;
        for (Character c : prefix.toCharArray())
        {
            if (p.ne == null) return false;
            if (!p.ne.containsKey(c)) return false;
            p = p.ne.get(c);
        }
        return true;
    }
}