一道经典的Trie Tree模板题,通过维护一个cnt数组记录在当前节点结束的字符串数量,最后统计全部搜索过程中每个节点cnt值得累加即可得到答案。
#include <bits/stdc++.h>
#define MAXN 1000000
using namespace std;
int n,m,tot;
int tire[MAXN][26];
int cnt[MAXN];
void insert(string x) {
int p = 0;
for(unsigned long int i = 0; i < x.length(); ++i) {
int ch = x[i] - 'a';
if(!tire[p][ch])
tire[p][ch] = ++tot;
p = tire[p][ch];
}
++cnt[p];
}
int search(string x) {
int p = 0,sum = 0;
for(unsigned long int i = 0; i < x.length(); ++i) {
p = tire[p][x[i] - 'a'];
if(!p)
break;
sum += cnt[p];
}
return sum;
}
int main() {
scanf("%d%d",&n,&m);
string x;
char temp[MAXN];
for(int i = 1; i <= n; ++i) {
scanf("%s",temp);
x = temp;
insert(x);
}
for(int i = 1; i <= m; ++i) {
scanf("%s",temp);
x = temp;
printf("%d\n",search(x));
}
return 0;
}