输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。
在20%的数据中n, m<=10，词典的字母表大小<=2.
在60%的数据中n, m<=1000，词典的字母表大小<=5.
在100%的数据中n, m<=100000，词典的字母表大小<=26.
本题按通过的数据量排名哦～
对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。
样例输入
5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab
样例输出
1 0 3 0 0
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 const int N=400005; 7 int trie[N][27]; 8 int sum[N]; 9 int tot; 10 int n,m; 11 char s[27]; 12 13 void Insert(){ 14 int len=strlen(s); 15 int root=0; 16 for(int i=0;i<len;i++){ 17 int id=s[i]-‘a‘; 18 if(!trie[root][id]) trie[root][id]=++tot; 19 sum[trie[root][id]]++; 20 root=trie[root][id]; 21 } 22 } 23 24 int Search(){ 25 int len=strlen(s); 26 int root=0; 27 for(int i=0;i<len;i++){ 28 int id=s[i]-‘a‘; 29 if(!trie[root][id]) return 0; 30 root=trie[root][id]; 31 } 32 return sum[root]; 33 } 34 35 int main() 36 { 37 scanf("%d",&n); 38 for(int i=1;i<=n;i++){ 39 scanf("%s",s); 40 Insert(); 41 } 42 scanf("%d",&m); 43 for(int i=1;i<=m;i++){ 44 scanf("%s",s); 45 printf("%d\n",Search()); 46 } 47 return 0; 48 }
原文：https://www.cnblogs.com/qq-1585047819/p/10981910.html
