标题真直接
题目大意
给你 $n$ 个字符串。存到一个字典中。又给你 $m$ 个询问，每个询问给一个字符串，在字典中查出有多少个字符串是以这个字符串为前缀。
解题思路
模板题啊
在每个点设置一个变量 $sig$ 表示有几个单词是以经过路径上的字符组成的串作为前缀的个数。
$Trie$ 树。在 $insert$ 操作时，把路径上经过的点的 $sig$ 加 $1$ 。
查询的时候直接输出 $sig$ 就是了
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m;
char s[
15];
struct node {
int sig;
node *nxt[
30];
}*
root;
inline node *
build() {
node *k =
new(node);
k->sig =
0;
memset(k->nxt, NULL,
sizeof(k->
nxt));
return k;
}
inline void insert(
char *
s) {
char *word =
s;
node *rt =
root;
int id;
while(*
word) {
id = *word -
'a';
if(rt->nxt[id] ==
NULL)
rt->nxt[id] =
build();
rt = rt->
nxt[id];
rt->sig ++
;
word ++
;
}
}
inline int query(
char *
s) {
node *rt =
root;
char *word =
s;
int id;
while (*
word) {
id = *word -
'a';
if(rt->nxt[id] ==
NULL)
return 0;
rt = rt->
nxt[id];
word ++
;
}
return rt->
sig;
}
int main() {
scanf("%d", &
n);
root =
build();
for(
int i=
1; i<=n; i++
) {
scanf("%s", s);
insert(s);
}
scanf("%d", &
m);
for(
int i=
1; i<=m; i++
) {
scanf("%s", s);
printf("%d\n", query(s));
}
return 0;
}
转载于:https://www.cnblogs.com/bljfy/p/9569577.html
相关资源：数据结构—成绩单生成器
