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. 复杂度分析操作时间复杂度空间复杂度插入所有 SiO(总长度)O(总长度 × 26)单次询问 TO(|T|)—整体O(总长度 Σ|T|)O(总长度 × 26)由于输入字符串总长度不超过 106Trie 节点数最多约为 106空间可以接受。整体时间复杂度为线性级别能够高效通过本题。5. 样例验证以样例输入为例3 2 ab bc abc abc efg插入 ab、bc、abc 后查询 abc从根节点依次匹配 a、b、c终点节点计数为 2ab 和 abc 都经过该路径输出 2。查询 efg根节点下没有 e 子节点输出 0。与样例输出一致。