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));
		}
	}
}