020（【模板】字典树）（字典树）

题目：https://www.luogu.com.cn/problem/P8306

题目思路：首先，从它的题目就可以看出来是用字典树做

先把前面一揽子字符串存起来再说

他要求问，给定的这个字符串是多少个前面的一揽子字符串的前缀

还记得字典树的特性吗？它那公共前缀被扔在一起的特性

由此联想，我们可以给每一个节点编上号码，“这个节点和它的那些顶头上司是几个字符串的前缀啊”

跟着这个思路，只需要再把后面那个给定的字符串搜一遍，它最后停在哪个节点，哪个节点所对应的号码就是它所对应的答案

怎么找？硬找。

每一个字符串只要经过这个节点，这个节点所对应的号码就加1

最开始把它们全部设置成0，不就成了。

再提一个醒，本题的字符在字典上并不连续

老老实实用ASCII码的属于徒增烦恼

用一个map即可，map，说白了就是一个谁都可以当下标的数组，就像一根有油的记号笔，目前多以一维的形式存在

#include
using namespace std;
int n,m1,m2,tot=0,id1=0;//id1最开始是0 
int trie[3000001][63],code[3000001];
//后面那个63是因为一共有62种字符 
string s; 
map<char,int>id;//ASCII码可以滚蛋了 
void putin(string s){//放进去 
	int s0=s.size(),p=0;
	for(int l=0;lif(!trie[p][id[s[l]]]){ 
			trie[p][id[s[l]]]=++tot;
		}
		p=trie[p][id[s[l]]];
		//上面都是字典树的基础
		//不知道的去看我的018博客 
		code[p]++; 
		//碰上了就代表“又多一个有联系的”
		//加上去 
	}
}
int finding(string s){
	//寻找 
	int s0=s.size(),p=0;
	for(int l=0;lif(!trie[p][id[s[l]]]){
			return 0;
			//断档了
			//意味着没有字符串有像他一样的前缀
			//Salut 
		}
		p=trie[p][id[s[l]]];
		//碰上了就接着往下走 
	}
	return code[p];
	//到地方，下车 
}
int main(){
	scanf("%d",&n);
	//编编编编号
	for(char i='a';i<='z';i++){
		id[i]=++id1;
	}
	for(char i='A';i<='Z';i++){
		id[i]=++id1;
	}
	for(char i='0';i<='9';i++){
		id[i]=++id1;
	}
	//编编编编号 
	while(n--){
		for(int i=0;i<=tot;i++){
			code[i]=0;
			for(int j=0;j<=63;j++){
				trie[i][j]=0;
			}
		}
		tot=0;
		//别忘了“全部设置成0” 
		scanf("%d%d",&m1,&m2);
		for(int i=1;i<=m1;++i){
			cin>>s;
			putin(s);
			//先把前面一揽子字符串打进去 
		}
		for(int i=1;i<=m2;++i){
			cin>>s;
			cout<endl;
			//找，完了出结果 
		}
	}
	return 0;
}

题目总结：再说一说我做题时候的血泪史
第一个，明明设置了一个for（l）然后转头来个 s[i]
第二个，在用tot之前把tot归零
第三个，（！（1）==0），令人无地自容的命令