题目

给定N个字符串S1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。
输入字符串的总长度不超过106，仅包含小写字母。
输入格式
第一行输入两个整数N，M。
接下来N行每行输入一个字符串Si。
接下来M行每行一个字符串T用以询问。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
输入样例：
3 2
ab
bc
abc
abc
efg
输出样例：
2
0

题解

题解传送门
- $trie$是一种用于字符串快速检索的多叉树结构。
- 初始化
1. 一个空的$trie$包含一个根节点，它的字符指针均指向空
- 插入
当我们需要插入一个字符串$s$时，我们令一个指针$p$最初指向根节点，扫描$s$中的每个字符$c$：
1. 若$p$的$c$字符指针指向一个已经存在的节点$q$，则令$p =q$
2. 若$p$的$c$字符指针指向空，则新建一个节点$q$，然后令$p$的$c$字符指针指向$q$，然后令$p=q$
当一个字符串检索完毕时，在当前节点$p$标记它是字符串的结尾。
- 查找
检索一个字符串$s$是否在$trie$中时， 令一个指针$p$指向根节点，然后依次扫描$s$中的每个字符$c$：
1. 若$p$的$c$字符指向空，说明$s$被插入到$trie$中，结束检索。
2. 若$p$的$c$字符指针指向一个已经存在的节点$q$，则令$p = q$
当$s$中的字符检索完毕时，若当前节点$p$被标记为一个字符串的末尾，则说明在$trie$中存在，否则说明$s$没有被插入到$trie$中
- 题解
对于本题来说因为要统计前缀，所以我们在插入过程中将原本标记$p$是字符串结尾个数组改成求和数组，在查询累加即可。

code

#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 1e6 + 100; 

int n, m, tot; 
int tail[maxn]; 
int a[maxn][30]; 

inline void insert(string s) {
    int p = 0; 
    for (int i = 0; i < s.size(); ++i) {
        int ch = s[i] - 'a'; 
        if (a[p][ch] == 0) a[p][ch] = ++tot; 
        p = a[p][ch]; 
    } 
    tail[p]++; 
}

inline int ask(string s) {
    int p = 0, ans = 0; 
    for (int i = 0; i < s.size(); ++i) {
        int ch = s[i] - 'a'; 
        p = a[p][ch]; 
        if (p == 0) return ans; 
        ans += tail[p]; 
    }
    return ans; 
}

int main() {
    cin >> n >> m; 
    string s;
    for (int i = 1; i <= n; ++i) {
        cin >> s; 
        insert(s); 
    }
    for (int i = 1; i <= m; ++i) {
        cin >> s; 
        printf("%d\n", ask(s)); 
    }
    return 0; 
}