题目
题目描述
给定
n
n
n 个模式串
s
1
,
s
2
,
…
,
s
n
s_1, s_2, \dots, s_n
s1,s2,…,sn 和
q
q
q 次询问，每次询问给定一个文本串
t
i
t_i
ti，请回答
s
1
∼
s
n
s_1 \sim s_n
s1∼sn 中有多少个字符串
s
j
s_j
sj 满足
t
i
t_i
ti 是
s
j
s_j
sj 的前缀。
一个字符串
t
t
t 是
s
s
s 的前缀当且仅当从
s
s
s 的末尾删去若干个（可以为 0 个）连续的字符后与
t
t
t 相同。
输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。
输入格式
本题单测试点内有多组测试数据。
输入的第一行是一个整数，表示数据组数
T
T
T。
对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数
n
n
n 和询问的个数
q
q
q。
接下来
n
n
n 行，每行一个字符串，表示一个模式串。
接下来
q
q
q 行，每行一个字符串，表示一次询问。
输出格式
按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。
样例 #1
样例输入 #1
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9
样例输出 #1
2
1
0
1
2
1
提示
数据规模与约定
对于全部的测试点，保证
1
≤
T
,
n
,
q
≤
1
0
5
1 \leq T, n, q\leq 10^5
1≤T,n,q≤105，且输入字符串的总长度不超过
3
×
1
0
6
3 \times 10^6
3×106。输入的字符串只含大小写字母和数字，且不含空串。
题解
这道题算是 普及/提高- 的题里面通过率较低的一道题了。
首先的首先（可跳过）
Trie树是什么？
“Trie” 翻译过来是 “排序” 的意思。
所以说———— “排序树” ？
好吧，都叫它 “字典树” 。
而它是干什么用的呢？
如果给你一堆字符串，然后问你某一个字符串是否存在，怎么办？
暴力枚举出…………（想多了）。
所以，这就需要用到trie树了。
如下图：
Trie树是一棵树。
根节点
r
o
o
t
root
root 为空，其它所有的子节点都包含了一个字符。
每个节点有一些不同的子节点。
这样，如果你想要在其中查找字符串 “ecea” 是否出现过，就只用从根节点开始，依次查询每一个对应的节点，就可以了。如果查询到某一个节点找不到对应的子节点，就说明不存在这个字符串；如果能查询完，这个字符串就是存在的。
如下图：
此外，我们还需要在每个字符串的末尾打上一个标记，来判断是否有以这个字符结尾的字符串。
再来看看这个题
给定
n
n
n 个模式串
s
1
,
s
2
,
…
,
s
n
s_1, s_2, \dots, s_n
s1,s2,…,sn 和
q
q
q 次询问，每次询问给定一个文本串
t
i
t_i
ti，请回答
s
1
∼
s
n
s_1 \sim s_n
s1∼sn 中有多少个字符串
s
j
s_j
sj 满足
t
i
t_i
ti 是
s
j
s_j
sj 的前缀。
一个字符串
t
t
t 是
s
s
s 的前缀当且仅当从
s
s
s 的末尾删去若干个（可以为 0 个）连续的字符后与
t
t
t 相同。
输入的字符串大小敏感。例如，字符串
Fusu和字符串fusu不同。
题目要求的是判断前缀。也要打标记
+
+
+ 插入
+
+
+ 查询。
再来细讲一下
1. Trie树的存储实现
-
s
o
n
son
son 数组用来存每个节点的子节点信息，
s
o
n
[
i
]
[
j
]
son[i][j]
son[i][j] 表示节点
i
i
i 有子节点
j
j
j 。
-
c
n
t
cnt
cnt 数组用来打标记，
c
n
t
[
i
]
cnt[i]
cnt[i] 记录以节点
i
i
i 结尾的字符串个数。
-
i
d
x
idx
idx 表示节点总数，在插入的时候每次
+
+
++
++ 。
const int N = 1000010;
int son[3 * N][65], cnt[3 * N], idx;
2. Trie树的每个子节点都只含大小写字母和数字
题目有要求：
对于全部的测试点，保证
1
≤
T
,
n
,
q
≤
1
0
5
1 \leq T, n, q\leq 10^5
1≤T,n,q≤105，且输入字符串的总长度不超过
3
×
1
0
6
3 \times 10^6
3×106。输入的字符串只含大小写字母和数字，且不含空串。
所以，写一个字符转换成数值的函数，方便存储。
int ctoi(char c){
int x;
if('A' <= c && c <= 'Z') x = c - 'A'; //大写字母对应 0 ~ 25
else if('a' <= c && c <= 'z') x = c - 'a' + 26; //小写字母对应 26 ~ 51，所以要减'a'，再加上26
else x = c - '0' + 52; //数字对应 52 ~ 61，同样的，减'0'再加上52
return x;
}
3. 插入字符串
在Trie树中插入一个字符串，也写一个函数。
void insert(char str[]){
int p = 0; //p用来暂时记录当前的节点编号
for(int i = 0; str[i]; ++i){ //循环字符串中的每一个字符
int u = ctoi(str[i]); //u是子节点的值
if(!son[p][u]) son[p][u] = ++idx;
//如果当前节点没有此子节点，新拓展一个子节点，并把节点总数加一，也作为新节点的编号
p = son[p][u]; //记录当前节点编号
++cnt[p]; //打标记，不再赘述
}
}
4.查询字符串
和插入类似。
int query(char str[]){
int p = 0; //同插入中的p
for(int i = 0; str[i]; ++i){ //同插入
int u = ctoi(str[i]); //同插入
if(!son[p][u]) return 0; //如果没有对应的子节点，也就是找不到，直接返回0
p = son[p][u]; //同插入
}
return cnt[p];
//返回字符串个数。这里注意，如果查找到了，但是没有打标记，返回的cnt[p]还是0
}
最后的最后（Code）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
char str[3 * N];
int son[3 * N][65],cnt[3 * N],idx;
int ctoi(char c){
int x;
if('A' <= c && c <= 'Z') x = c - 'A';
else if('a' <= c && c <= 'z') x = c - 'a' + 26;
else x = c - '0' + 52;
return x;
}
void insert(char str[]){
int p = 0;
for(int i = 0; str[i]; ++i){
int u = ctoi(str[i]);
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
++cnt[p];
}
}
int query(char str[]){
int p = 0;
for(int i = 0; str[i]; ++i){
int u = ctoi(str[i]);
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int t;
int main(){
scanf("%d",&t);
while(t--){
for(int i = 0; i <= idx; ++i)
for(int j = 0; j <= 64; ++j)
son[i][j] = 0;
for(int i = 0; i <= idx; i++)
cnt[i] = 0;
//每组数据前清空数组
idx = 0;
int n,q;
scanf("%d%d", &n, &q);
while(n--){
scanf("%s", str);
insert(str);//插入
}
while(q--){
scanf("%s", str);
printf("%d\n", query(str));//查询
}
}
return 0;
}
真的最后了？
这是蒟蒻的第一篇题解，很详细了(自信) 。
请多多支持。
