Trie树

1、思路

用树的结构来存储字符串

2、代码模板

#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N],idx;			//每个节点最多有26个边，cnt是以这个点结尾的字符串个数，idx是当前用到的下标
									//下标是0的点，既是根节点，又是空节点 
char str[N]; 
void insert(char str[])
{
	int p=0;						//当前走到了哪里 
	for(int i=0;str[i];i++)			//字符串结尾是\0可以用来判断 
	{
		int u=str[i]-'a';			//a~z映射为0~25 
		if(!son[p][u])
			son[p][u]=++idx;
		p=son[p][u];				//当前走到了son[p][u] 
	}	
	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=son[p][u];				//找到了就进一步 
	} 
	return cnt[p];					
}

int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		char op[2];
		scanf("%s%s",op,str);
		if(op[0]=='I')
			insert(str);
		else
			printf("%d\n",query(str));
	}	
	return 0;
}