P8306 【模板】字典树

题目描述

给定 n 个模式串 s1​,s2​,…,sn​ 和 q 次询问，每次询问给定一个文本串 ti​，请回答 s1​∼sn​ 中有多少个字符串 sj​ 满足 ti​ 是 sj​ 的前缀。

一个字符串 t 是 s 的前缀当且仅当从 s 的末尾删去若干个（可以为 0 个）连续的字符后与 t 相同。

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

输入格式

输入的第一行是一个整数，表示数据组数 T。

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 n 和询问的个数 q。
接下来 n 行，每行一个字符串，表示一个模式串。
接下来 q 行，每行一个字符串，表示一次询问。

输出格式

按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

输入输出样例

输入

3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9

输出

2
1
0
1
2
1

做字典树的模版题，先要了解字典树怎么用

比如我们要存储一些单词

cat car busy bus

我们可以建一棵树来存它们，这棵树的根节点为零

对于这道题，我们借助上图弄清思路

在输入模式串的时候，就根据上图的思路，按字符串每一位查找，并且存储

查询的时候，就一步一步在树中找，如果找到叶子结点了，但查询的单词没找完，就说明它不是已出现字符串的前缀，如果找完了字符串，就说明是

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int t;
int n,m;
int ch[N][124];
int cnt[N];
int idx=0;
void in(string s){int p=0;for(int i=0;i<s.length();i++){int j=int(s[i]);if(!ch[p][j])ch[p][j]=++idx;p=ch[p][j];cnt[p]++;}
}
int out(string s){int p=0;for(int i=0;i<s.length();i++){int j=int(s[i]);if(!ch[p][j])return 0;p=ch[p][j];}return cnt[p];
}
signed main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);string s;for(int i=0;i<=idx;i++){cnt[i]=0;for(int j=0;j<=123;j++){ch[i][j]=0;}}idx=0;for(int i=1;i<=n;i++){cin>>s;in(s);}for(int i=1;i<=m;i++){cin>>s;printf("%d\n",out(s));}}
}