数据结构（Trie树（字典树））

        今天没有例题，只是分享一个字典树的模板，之后我打算学一下AC自动机和网络流有关的内容，这两个好像都挺难的，作为AC自动机的前置内容，就提前分享一下Trie树的学习心得。

        字典树，名字里有个字典，那么他和字典有什么关系呢？

        我们回想一下我们是怎么查字典的（这里就拿查英语单词举例子，毕竟英语烂，比赛都要靠字典续命，中字字典好久没用过了），我们会先找到首字母的区域，而后在这个区域内依次找接下来的字母，那么你就已经能够了解Trie树的构造了。

        Trie树就像一部字典一样，从根节点的叶子节点，一条链构成一个或几个完整的单词（注意是一个或几个，比如像busy,bus,在busy串里会有bus的包含），那么该如何实现呢？

        我们需要一些数组来存储并维护，ch数组，存储的是叶子信息，cnt数组存储的是完整的单词在文本中出现的次数，s是读取文本信息，但是众所周知，字母是有顺序的，ch数组如果存储的是字母信息，怎么将信息传递下去呢？

        谁说ch一定要存字母信息了。先来看看我是怎么初始化的吧：

char s[N];
int ch[N][26], cnt[N], idx;

        26？怎么这么眼熟，这里我们采用的是将字母映射为索引的方法，通过记录索引来反映我们这一位是什么字母，a对应0，b对应1······所以我们引入了idx来标记我们当前字母的位次。

        当树为空或者说当前首字母并未出现在根下时，我们要开一个新根去存储当前单词链，同理，当我们有首字母但是没有找到想要的接下去字母时，我们就从断点长出一条新的链，是不是就是我们查字典的方法？

        代码如下：

void insert(char *s)
{
	int p = 0;
	for(int i = 0; s[i]; i ++)
	{
		int j = s[i] - 'a';
		if(!ch[p][j])
			ch[p][j] = ++ idx;
		p = ch[p][j];
	}
	cnt[p] ++;
}

        但是注意到了末尾的cnt++操作，上面我们说到要存储单词出现的个数，cnt就是为此而生的，当我们完整记录下一个单词后，在末尾字母处记录下次数，就算出现busy和bus这样的情况也不会互相影响。

        以上是存储的内容，查询其实也是如此，就像查字典一样，从根到尾。如果找不到某一个字母，就表明它就没有出现过。

        代码如下：

void query(char *s)
{
	int p = 0;
	for(int i = 0; s[i]; i ++)
	{
		int j = s[i] - 'a';
		if(!ch[p][j])
			return 0;
		p = ch[p][j];
	}
	return cnt[p];
}

        之后要学一下AC自动机和网络流，虽然学长说这些都是金牌题，但是我感觉还是要逼自己一下的，毕竟技能树先多点点>_<.