1. 题目分析
本题要求统计在给定的 N 个字符串中，有多少个字符串是询问串 T 的前缀。输入字符串总长度不超过 106，仅包含小写字母，N 和 M 最大均为 105。
朴素做法是对于每个询问 T，遍历所有 Si 逐一判断是否为前缀，时间复杂度为 O(N × |T|)，在数据规模较大时会超时。因此需要更高效的数据结构。
2. 解题思路：Trie 字典树
Trie（字典树）非常适合处理前缀匹配问题。我们将所有 Si 插入一棵 Trie 树，并在每个节点记录「经过该节点的字符串数量」。这样，对于询问 T，只需沿着 Trie 从根节点向下走，若能完整走完 T 的所有字符，则终点节点记录的计数就是答案；若中途某个字符不存在，则答案为 0。
具体步骤如下：
- 建立 Trie 根节点，每个节点包含 26 个子节点指针（对应 26 个小写字母）和一个计数变量 cnt。
- 插入每个 Si 时，沿途经过的每个节点 cnt 加 1，表示该节点作为前缀被多少个字符串经过。
- 查询 T 时，从根节点出发，依次匹配 T 的每个字符。若某字符对应的子节点不存在，直接返回 0；否则继续向下，最终返回终点节点的 cnt。
3. C++ 代码实现
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 5; int trie[MAXN][26], cnt[MAXN], tot = 0; void insert(const string& s) { int u = 0; for (char c : s) { int v = c - 'a'; if (!trie[u][v]) trie[u][v] = ++tot; u = trie[u][v]; cnt[u]++; } } int query(const string& s) { int u = 0; for (char c : s) { int v = c - 'a'; if (!trie[u][v]) return 0; u = trie[u][v]; } return cnt[u]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; string s; for (int i = 0; i < n; i++) { cin >> s; insert(s); } for (int i = 0; i < m; i++) { cin >> s; cout << query(s) << '\n'; } return 0; }4. 复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 插入所有 Si | O(总长度) | O(总长度 × 26) |
| 单次询问 T | O(|T|) | — |
| 整体 | O(总长度 + Σ|T|) | O(总长度 × 26) |
由于输入字符串总长度不超过 106，Trie 节点数最多约为 106，空间可以接受。整体时间复杂度为线性级别，能够高效通过本题。
5. 样例验证
以样例输入为例：
3 2 ab bc abc abc efg插入 ab、bc、abc 后，查询 abc：从根节点依次匹配 a、b、c，终点节点计数为 2（ab 和 abc 都经过该路径），输出 2。查询 efg：根节点下没有 e 子节点，输出 0。与样例输出一致。
