P8306 【模板】字典树

字典树树简介

字典树英文名为 \(Trie\) 树，就是像字典一样的树。

字典树树正文

我们建一棵树，边表示字母和数字，节点表示根到此节点的字符串，假设有某个点，其子节点表示在这个字符串上再加一个字母的字符串。

那么这样如何解决这道题呢？

首先我们要根据题目给定的字符串建立这棵字典树：

void push_in(string & s){
	int now=0;
	for(int i=0;i<s.size();i++){
		cnt[now]++;
		int t=getid(s[i]);
		if(nxt[now][t]==-1) {
			nxt[now][t]=++all;
		}
		now=nxt[now][t];
	}
	cnt[now]++;
}
for(int i=1;i<=n;i++)push_in(s[i]);

然后题目每次询问给定一个字符串 \(t\)，问其是几个字符串的前缀，我们在建立树时记录了一个 cnt 数组，表示其子树大小，我们按照树的路径取寻找字符串 \(t\) 的位置，然后看这个位置的子树大小就知道答案了。

int find(string & s){
	int now=0;
	for (int i=0;i<s.size();i++){
		int t=getid(s[i]);
		if(nxt[now][t]==-1)return 0;
		now=nxt[now][t];
	}
	return cnt[now];
}

最后就是一些杂碎的输入输出了，我贴上完整代码加注释：

#include<bits/stdc++.h>
using namespace std;
int all,n,q;
string s[100005];
int nxt[3000006][70];
int cnt[3000006];
int getid(char c){
	if(c>='0'&&c<='9')return c-'0';//数字编号0-9
	else if(c>='a'&&c<='z')return c-'a'+10;//小写字母编号10-35
	else return c-'A'+36;//大写字母编号36-61
}
void push_in(string & s){//建立字典树
	int now=0;
	for(int i=0;i<s.size();i++){
		cnt[now]++;//子树节点个数+1
		int t=getid(s[i]);//给字符编号
		if(nxt[now][t]==-1) {//没有这个分支就开设一条
			nxt[now][t]=++all;
		}
		now=nxt[now][t];//循着前“人”开设的路径找
	}
	cnt[now]++;
}
int find(string & s){//搜寻答案
	int now=0;
	for (int i=0;i<s.size();i++){
		int t=getid(s[i]);
		if(nxt[now][t]==-1)return 0;//找不到这个字符串
		now=nxt[now][t];//循着路径找
	}
	return cnt[now];//返回子树大小
}
int main(){
	int t;cin>>t;
	while(t--){//多组测试数据
		cin>>n>>q;
		int kkk=0;
		for(int i=1;i<=n;i++){
			cin>>s[i];//读入
			kkk+=s[i].size();//计算总长度
		}
		for (int i=0;i<=kkk+10;i++){//清空
			cnt[i]=0;
			for(int j=0;j<=62;j++){
				nxt[i][j]=-1;
			}
		}
		for(int i=1;i<=n;i++){//建树
			push_in(s[i]);
		}
		while(q--){
			string o;cin>>o;
			cout<<find(o)<<endl;
		}
		all=0;
	}
	return 0;//完美结束！！
}