trie树

输入

输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。

在20%的数据中n, m<=10，词典的字母表大小<=2.

在60%的数据中n, m<=1000，词典的字母表大小<=5.

在100%的数据中n, m<=100000，词典的字母表大小<=26.

输出

对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

样例输入
5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab
样例输出
1
0
3
0
0
 

#include<iostream>
#include<cstdio>
#include<cstring>
 
using namespace std;
 
int trie[1000010][26] = {0}; //trie[i][j]=k,表示i号节点与k号节点相连,边为j号字符; k=0表示没有边相连
int color[1000010] = {0}; //color[i]=1 表示i号节点是终止节点（本题未用到）
int cnt[1000010] = {0}; //cnt[i] 表示i号节点为根节点的子树中有多少个终节点，即可知以它为前缀的字符串有多少个（本题要求）
int k = 1;
 
void insert(char *a)
{
	int s = 0;
	int len = strlen(a);
	for(int i=0;i<len;i++)
	{
		int c = a[i]-'a';
		if(trie[s][c]==0)
		{
			trie[s][c] = k;
			k++;
		}
		s = trie[s][c];
		cnt[s]++;
	}
	//color[s] = 1;
}
 
int search(char *a)
{
	int s = 0;
	int len = strlen(a);
	for(int i=0;i<len;i++)
	{
		int c = a[i]-'a';
		if(trie[s][c]==0)
		{
			return 0;
		}
		s = trie[s][c];
	}
	//return s == 1;
	return cnt[s];
}
 
int main()
{
	
	int n;
	char a[20];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",a);
		insert(a);
	}
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",a);
		printf("%d\n",search(a));
	}
 
	return 0;
}

理解trie 树：https://www.bilibili.com/video/av58431163