Tire树

Trie树

trie树又叫字典树，主要是用来存储字符串的，可以实现快速的查找字符串

类似于这种结构，这里面能找到的字符串就是see pain pand dog

实现模板

	int son[N][26], cnt[N], idx;
	// 0号点既是根节点，又是空节点
	// son[][]存储树中每个节点的子节点
	// cnt[]存储以每个节点结尾的单词数量

	// 插入一个字符串
	void insert(char *str)
	{
		int p = 0;
		for (int i = 0; str[i]; i ++ )
		{
			
			int u = str[i] - 'a';
			if (!son[p][u]) son[p][u] = ++ idx;
			p = son[p][u];
		}
		cnt[p] ++ ;
	}

	// 查询字符串出现的次数
	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];
	}

这里全局定义了几个变量 分别是 son 数组，cnt数组，idx变量
简单解释一下，
idx表示当前这个节点是这棵树的第几个插入的字符节点，假如说插入的第一个字符串是apple，那么a的idx是0，p的idx是1
son[p][u] = j 表示 第 idx = p 个节点的子节点字母为 u+‘a’ 且子节点的idx为 j
cnt[i]表示idx为i的字符是cnt[i]个字符串的尾巴，比如第一个字符串插入了一个apple,那么cnt[4]++.apple插入的过程就是：
插入apple，则son[0][0] = 1; 然后给son[1][15] = 2;son[2][15] = 3; son[3][11] = 4; son[4][4] = 5;
第二个插入good
son[0][6] = 6; son[6][14] = 7; son[7][14] = 8, son[8][3] = 9;
依次插入apple good great以后son数组内存表示：

树状图表示：

插入过程：代码思路就是：
先令 p = 0;从根节点的处开始找，如果不存在当前的字符，则创建它，然后把idx++也就是下一个字符的序号赋给它，如果存在则直接p = son[p][u] 匹配树状图中的 下一个字符。
最后如果到了要搜索字符串的末尾，则cnt自加；