题目描述
给定N个字符串$S_1,S_2…S_N$,接下来进行M次询问,每次询问给定一个字符串T,求$S_1~S_N$中有多少个字符串是T的前缀。
输入字符串的总长度不超过$10^6$,仅包含小写字母。
样例
输入样例:
3 2
ab
bc
abc
abc
efg
输出样例:
2
0
算法1
(Trie树) $O(mn)$
1.首先对输入的字符串建Trie树。
2.对询问的字符串在Trie树中进行查找。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 5e6 + 10, M = 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 query(){
int p = 0, res = 0;
for (int i = 0; str[i]; i ++){
int s = str[i] - 'a';
if (!son[p][s]) break;
p = son[p][s];
res += cnt[p];
}
return res;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++){
scanf("%s", str);
insert();
}
while (m --){
scanf("%s", str);
printf("%d\n", query());
}
return 0;
}