一种经典的数据结构

用于存储查找一个集合中有多少相同的字符串

如下是5个字符串的Trie树：其中红色星星代表有以该字符结尾的字符串存在，root是他们的根结点，默认根结点存在26个字母，只有以该根结点存在的字幕存在时才有显示，但默认所有根结点的值都为1，如a和b和c都是根结点，作为根结点的值都为0，但是d~z的根节点仍然为0，只是未显示而已

 

而trie树最常用的就是插入字符串和查询字符串数量的操作了

插入字符串：

1.从根节点root开始查询是否有该字符串的存在，如果没有则创建，如果有则更新进入下一步继续判断

2.当插入完成后，在最后一个点处将该字符串数量加1

查询字符串：

1.与插入类似，从根节点开始查询是否存在，如果整个查询中存在一次某字符不存在，则返回0

2.如果所有查询均存在，则返回最后的查询点代表的数量值作为该字符串在trie树中的总数量

 

具体实现

以一道模板题为实现例 Acwing 835 字符串统计

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 100010; //插入的字符串中的字符总数 
char str[N];

int son[N][26]; //每个结点都有26种可能，N代表当前的位置
int cnt[N]; //进行字符串数量的统计，即如图记录图中星星的位置的总值
int idx; //从第一个字符开始记录 插入的 不重复的字符串的 字符总数

void insert(char str[]){
	int p = 0; //每次都从根结点开始
	for(int i = 0; str[i]; i++){ //用str[i]是否为'\0'判断字符串长度
		
		int u = str[i] - 'a';
		if(!son[p][u]) son[p][u] = ++idx; //如果该结点的字符不存在，那么我就创建 
		
		/*如果该结点的字符是存在的，那么我就直接进入到下一步更新p的位置
		注：如果每一结点的字符均存在，那么就代表有重复字符串插入了，这时候就无需创建了，只要使cnt[p]++即可 
		*/
		
		p = son[p][u]; //更新位置p，进行下面的字符插入操作 
	} 
	
	cnt[p]++; //每次的插入操作结束后，以p最后的位置标记，将该字符串数量加1 
} 

int query(char str[]){
	int p = 0;
	for(int i = 0; str[i]; i++){
		
		int u = str[i] - 'a';
		
		if(!son[p][u]) //如果存在查询过程中某字符串的某个字符不存在，则该字符串必定不存在
			return 0;
		
		//如果存在，更新p的位置 
		p = son[p][u]; 
	}
	
	return cnt[p]; //如果存在，返回字符串的个数 
}

int main()
{
	int n;
	scanf("%d", &n);
	
	while(n--){
		char op[2];
		//这里用%s处理输入，解决不必要的空格/换行输入麻烦 
		scanf("%s%s", op, str);
		
		if(op[0] == 'I') insert(str);
		else printf("%d\n", query(str)); 
	} 
}