题目描述
给定N个字符串S_{1},S_{2}...S_{n}S1?,S2?...Sn? ，接下来进行M次询问，每次询问给定一个字符串T，求S1~Sn 中有多少个字符串是T的前缀。输入字符串的总长度不超过10^6 ，仅包含小写字母。
输入描述:
第一行两个整数N，M。接下来N行每行一个字符串Si。接下来M行每行一个字符串表示询问。
输出描述:
对于每个询问，输出一个整数表示答案
思路：
一看到字符串的前缀,我们就应该想到字典树,和字典一样的前缀树.这道题是字典树很经典的一道题也没什么好说的。
完整C++版AC代码：
#include <iostream> #include <algorithm> using namespace std; const int N = 1000010; int n,m; int son[N][26], cnt[N], idx; char str[N]; void insert() { int p = 0; for (int i = 0; str[i]; i++) { int s = str[i] - ‘a‘; if (!son[p][s]) son[p][s] = ++idx; p = son[p][s]; } cnt[p]++; } int search() { int p = 0, ans = 0; for (int i = 0; str[i]; i++) { int s = str[i] - ‘a‘; if (!son[p][s]) break; p = son[p][s]; ans += cnt[p]; } return ans; } int main() { ios::sync_with_stdio; cin >> n >> m; while (n--) { cin >> str; insert(); } while (m--) { cin >> str; int ans = search(); cout << ans << endl; } return 0; }
原文：https://www.cnblogs.com/Mashiro-zBlog/p/11433436.html