1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

/**
     * trie[p][i]: 字典树的节点存储。
     * 第一维 p 代表节点的编号（行号）；
     * 第二维 i 代表字符的映射索引（0-51）。
     * 值存储的是该字符指向的下一个节点的编号。
     */
    private static int[][] trie = new int[1000005][52];

    /**
     * count[p]: 前缀统计的核心。
     * 记录有多少个模式串在插入过程中经过了编号为 p 的节点。
     * 因为我们要统计“以某串为前缀的个数”，所以每经过一个点都要加1。
     */
    private static int[] count = new int[1000005];

    /**
     * nodes: 记录当前字典树已经创建的节点总数。
     * 编号 0 始终代表根节点（不存储具体字符）。
     */
    private static int nodes = 0;

    public static void main(String[] args) throws IOException {
        // 使用高效的输入输出流处理百万级数据，防止超时
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取第一行：模式串数量 n 和查询次数 q
        String[] strA = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(strA[0]);
        int q = Integer.parseInt(strA[1]);

        // 1. 构建字典树阶段
        for (int i = 0; i < n; i++) {
            insert(br.readLine().trim());
        }

        // 2. 查询阶段
        for (int i = 0; i < q; i++) {
            // 直接输出以该文本串为前缀的模式串数量
            out.println(query(br.readLine().trim()));
        }

        // 刷新缓冲区并释放资源
        out.flush();
        out.close();
        br.close();
    }

    /**
     * 将字符映射到 0-51 的索引空间。
     * 区分大小写：'A'-'Z' 映射到 0-25，'a'-'z' 映射到 26-51。
     */
    private static int getIndex(char c) {
        return c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a' + 26;
    }

    /**
     * 模式串插入方法
     * 核心逻辑：沿着路径在每个经过的节点打标记计数。
     */
    private static void insert(String s) {
        int p = 0; // 从根节点 (编号 0) 开始
        for (char c : s.toCharArray()) {
            int i = getIndex(c);
            // 如果当前字符在当前节点下没有对应的子节点，则新建一个
            if (trie[p][i] == 0) {
                trie[p][i] = ++nodes;
            }
            // 移动到子节点
            p = trie[p][i];
            /**
             * 关键：只要经过这个节点，count 就自增。
             * 这样 count[p] 就代表了有多少个单词是以“从根到当前点”这一串字符为前缀的。
             */
            count[p]++;
        }
    }

    /**
     * 文本串查询方法
     * 核心逻辑：在字典树中顺着文本串寻找路径，若能走完路径，返回最后的 count。
     */
    private static int query(String t) {
        int p = 0; // 从根节点开始
        for (char c : t.toCharArray()) {
            int i = getIndex(c);
            /**
             * 如果在路径中发现某个字符没有对应的分支，
             * 说明没有任何一个模式串包含这个前缀，直接返回 0。
             */
            if (trie[p][i] == 0) {
                return 0;
            }
            p = trie[p][i]; // 顺着路径向下走
        }
        /**
         * 成功走完文本串 t 的所有字符，
         * 此时节点 p 的 count 值就是在插入阶段经过该点的字符串总数。
         */
        return count[p];
    }